I know if I reduce an NP-complete problem to a unknown problem P then I'm sure that P is itself NP-complete. And I know if I reduce a Problem P to an NP-complete problem there is no conclusion. So I want to give an example to show that we can reduce a Polynomial solvable problem P to an NP-complete one.
example of reduction a polynomial decision to an NP-complete
1k Views Asked by user3070752 At
1
There are 1 best solutions below
Related Questions in COMPLEXITY-THEORY
- MySQL Select Rank
- When dealing with databases, does adding a different table when we can use a simple hash a good thing?
- Push mysql database script to server using git
- Why does mysql stop using indexes when date ranges are added to the query?
- Google Maps API Re-size
- store numpy array in mysql
- Whats wrong with this query? Using ands
- MySQL-Auto increment
- show duplicate values subquery mysql
- Java Web Application Query Is Not Working
Related Questions in NP-COMPLETE
- MySQL Select Rank
- When dealing with databases, does adding a different table when we can use a simple hash a good thing?
- Push mysql database script to server using git
- Why does mysql stop using indexes when date ranges are added to the query?
- Google Maps API Re-size
- store numpy array in mysql
- Whats wrong with this query? Using ands
- MySQL-Auto increment
- show duplicate values subquery mysql
- Java Web Application Query Is Not Working
Related Questions in NP-HARD
- MySQL Select Rank
- When dealing with databases, does adding a different table when we can use a simple hash a good thing?
- Push mysql database script to server using git
- Why does mysql stop using indexes when date ranges are added to the query?
- Google Maps API Re-size
- store numpy array in mysql
- Whats wrong with this query? Using ands
- MySQL-Auto increment
- show duplicate values subquery mysql
- Java Web Application Query Is Not Working
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?
No, this is not well formulated. If an NP-complete problem A is reducible to a problem P all we can say is that any problem in NP is reducible to P. To say that P is NP-complete we need to know additionally that P is itself in NP.
What you probably intended to say was
Now to your original question.
Consider the problem known as 2-SAT: Given a boolean formula in conjunctive normal form such that each disjunction contains at most two variables tell it if is satisfiable.
Solving this problem following an algorithm by Aspvall, Plass & Tarjan (1979) involves building an implication graph and finding all its strongly connected components. The paper proves that the formula is satisfiable if and only if the implication graph does not contain a strongly connected component that include some variable together with its negation. It also shows that this algorithm is linear in the size of the formula encoding.
So
This gives an example of a polynomially solvable problem (2-SAT) that is reducible to an NP-complete problem (SAT).