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
987 views Asked by user3070752 At
1
There are 1 answers
Related Questions in COMPLEXITY-THEORY
- Ajax jQuery firing multiple time display event for the same result
- Implement Onfailure in webApi controller
- AJAX PHP - Reload div after submit
- ajax load data from mysql
- Ajax-update only a component attribute, not the whole component nor its children
- using ajax to get a php database result and then show the result in a button
- How to prevent browser from executing some JavaScript when person clicks Back button?
- ajax async: true statement execution order
- Rails 4.2 jQuery loads only after refresh
- WebForms GET Json requests (JsonRequestBehavior.AllowGet)
Related Questions in NP-COMPLETE
- Ajax jQuery firing multiple time display event for the same result
- Implement Onfailure in webApi controller
- AJAX PHP - Reload div after submit
- ajax load data from mysql
- Ajax-update only a component attribute, not the whole component nor its children
- using ajax to get a php database result and then show the result in a button
- How to prevent browser from executing some JavaScript when person clicks Back button?
- ajax async: true statement execution order
- Rails 4.2 jQuery loads only after refresh
- WebForms GET Json requests (JsonRequestBehavior.AllowGet)
Related Questions in NP-HARD
- Ajax jQuery firing multiple time display event for the same result
- Implement Onfailure in webApi controller
- AJAX PHP - Reload div after submit
- ajax load data from mysql
- Ajax-update only a component attribute, not the whole component nor its children
- using ajax to get a php database result and then show the result in a button
- How to prevent browser from executing some JavaScript when person clicks Back button?
- ajax async: true statement execution order
- Rails 4.2 jQuery loads only after refresh
- WebForms GET Json requests (JsonRequestBehavior.AllowGet)
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?
Popular Tags
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)
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).