I'm seeing a lot conflicting info about this problem. With some saying sites it is NP-complete and others saying that it is co-NP-complete. The only real consistent info I can find is that is definitely NP-hard. Which is it? And why?
Is MAX 3 SAT NP-complete or co-NP-complete?
1.5k Views Asked by STaron1 At
1
There are 1 best solutions below
Related Questions in COMPLEXITY-THEORY
- C++ using std::vector across boundaries
- Linked list without struct
- Connecting Signal QML to C++ (Qt5)
- how to get the reference of struct soap inherited in C++ Proxy/Service class
- Why we can't assign value to pointer
- Conversion of objects in c++
- shared_ptr: "is not a type" error
- C++ template using pointer and non pointer arguments in a QVector
- C++ SFML 2.2 vectors
- Lifetime of temporary objects
Related Questions in NP
- C++ using std::vector across boundaries
- Linked list without struct
- Connecting Signal QML to C++ (Qt5)
- how to get the reference of struct soap inherited in C++ Proxy/Service class
- Why we can't assign value to pointer
- Conversion of objects in c++
- shared_ptr: "is not a type" error
- C++ template using pointer and non pointer arguments in a QVector
- C++ SFML 2.2 vectors
- Lifetime of temporary objects
Related Questions in SAT
- C++ using std::vector across boundaries
- Linked list without struct
- Connecting Signal QML to C++ (Qt5)
- how to get the reference of struct soap inherited in C++ Proxy/Service class
- Why we can't assign value to pointer
- Conversion of objects in c++
- shared_ptr: "is not a type" error
- C++ template using pointer and non pointer arguments in a QVector
- C++ SFML 2.2 vectors
- Lifetime of temporary objects
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
I think this depends on how you define MAX-3SAT.
If you define MAX-3SAT as the function problem "given a 3CNF formula, produce a variable assignment maximizing the number of satisfied clauses," then it's neither NP-complete nor co-NP-complete. NP and co-NP are classes of decision problems and therefore no function problem can belong to them. Therefore, MAX-3SAT can't belong to NP or co-NP, so it can't be a complete problem for either class. This function problem is NP-hard via a reduction from vanilla 3SAT - if you could find the maximally satisfying assignment, you could check if the original formula was satisfiable by seeing if all clauses were satisfied.
You could also define MAX-3SAT as the decision problem "given a 3CNF formula and a number n, determine whether there's a variable assignment to the formula that makes at least n clauses true." This is definitely in NP and also NP-complete via a reduction from 3SAT.
On the other hand, if you define MAX-3SAT as the decision problem "given a 3CNF formula and a variable assignment to that formula, is that assignment the one that maximizes the number of satisfied clauses?," then it would belong to co-NP (if the answer is no, you could confirm this by exhibiting a better satisfying assignment). I'm not sure if it would be NP-hard, though, and I'm also not sure whether it's co-NP-hard either.
Hope this helps!