تقرير
A Note On The Natural Range Of Unambiguous-SAT
| العنوان: | A Note On The Natural Range Of Unambiguous-SAT |
|---|---|
| المؤلفون: | Pay, Tayfun |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Complexity, F.1.0 |
| الوصف: | We discuss the natural range of the Unambiguous-SAT problem with respect to the number of clauses. We prove that for a given Boolean formula in precise conjunctive normal form with n variables, there exist functions f(n) and g(n) such that if the number of clauses is greater than f(n) then the formula does not have a satisfying truth assignment and if the number of clauses is greater than g(n) then the formula either has a unique satisfying truth assignment or no satisfying truth assignment. The interval between functions f(n) and g(n) is the natural range of the Unambiguous-SAT problem. We also provide several counting rules and an algorithm that determine the unsatisfiability of some formulas in polynomial time. Comment: Replacement: The example at the end of section four was missing several clauses. This was fixed. The result did not change. There were several instances where a word was added or removed from a sentence. This also did not change any results |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2306.14779 |
| رقم الأكسشن: | edsarx.2306.14779 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |