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
- Given partially sorted array of type x<y => first apperance of x comes before first of y, sort in average O(n)
- What's the complexity of `+=` for a string in Python
- How to find big o of dependent loops and recursive functions?
- Understanding Unary PCP Reduction to a Matching Problem (UPCP)
- How to determine the time complexity of a recursive function that has a loop enclosed in it?
- Does the square root of an input lie in the middle of that input?
- Hash Table creation runtime complexity
- Optimization - Algorithm for finding load set combination that returns the maximum Von Mises stress
- Time complexity of a divide and conquer algorithm that searches for a value in an n x m table, rows and columns are sorted
- Big O notation of string permutation in Python
- finding the time complexity of the program
- how do i find the time complexity (big O) of this triple loop?
- determine the big o running time of the method
- Reduction from Hamiltonian path to Tripartite decision problem
- How to implement the Sosic and Gu linear algorithm for the n-queens problem
Related Questions in NP-COMPLETE
- Implementation of distributed greedy algorithm for finding maximum independent set
- K-Hamiltonian Path problem and NP-completeness
- Computational Learning Problem: 3-DNF Reduction
- Distributing marbles into buckets for maximal colour sharing
- Get all subsets of fairly large set of elements, {1,2,3,...,254,255}, that sum up to a value 666
- 3 partition np completeness
- P=NP in Exponential Space?
- AMPL variable in such-that part of set specification
- Best practice to search for a list of subset holders that holds a subset of a complete set?
- Judge:Some N P -complete problems have polynomial time algorithms, but some others do not
- Independent Set with dist(u, w) > 2
- proof of SAT np completeness
- What problem type the Power Set belong to?
- Are these two definitions of an NP-Complete problem equivalent?
- What would be considered the number of elements in a boolean satisfiability problem?
Related Questions in NP-HARD
- Algorithm for comparing two sets of sets
- How to solve the problem of assigning products to assembly lines
- matrix not updating in knapsack algorithm
- Constructing result for given word's order and overlapping in Shortest Superstring Problem
- Maximum independet set of size >= |E|
- Example of 3CNF to Hitting set conversion
- Distributing marbles into buckets for maximal colour sharing
- Fast approximation of simple cases of relaxed bipartite dimension of graph problem
- How do we, or can we, show many-one reduction of 3-SAT to a decision problem X when X takes an input that itself is exponentially long?
- Use Dynamic Programming (memoization) to get this function below 2^n time complexity
- What is the difference between 1D-, 2D and 3D Bin packing problem?
- proof of SAT np completeness
- Pick subset of items minimizing the count of the most frequent of the selected item's labels
- What problem type the Power Set belong to?
- Is this assignment problem with constrains NP-hard?
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).