If P != NP, are there then more Polynomial problems than SuperPolynomial problems, or vice versa?
If P != NP, are there more P than non-P problems or vice versa?
207 Views Asked by Albert Hendriks 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
- How do I implement the np.argmin function for several dimensions
- i installed numpy 1.26.3 but still not able to use np. method
- K-Hamiltonian Path problem and NP-completeness
- Computational Learning Problem: 3-DNF Reduction
- Editing a clique into a k-plex optimally is NP?
- NP hardness of bin packing with a fixed number of bins
- Example of 3CNF to Hitting set conversion
- Fast algorithm for n-rooks completion puzzle
- Deconstruct a column with dict values into multiple columns in pandas
- How to optimize this set-picking algorithm?
- np.where group multiple columns and pivot
- Getting error: "You must be logged in. Use `npm login` and try again." when trying to publish with NP
- np.load from relative file in the python package
- Searching Algorithm: Product Knapsack Problem with goal to find lowest product above a certain threshold?
- Authentic List of NP, NP Complete and NP Hard problems
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?
From a formal languages perspective, there are only countably many problems in P and uncountably many problems not in P. Every problem in P can be solved by a deterministic, polynomial-time Turing machine, and since the number of TMs is countably infinite, the number of languages in P is countably infinite. On the other hand, the number of total languages is equal to the number of possible subsets of strings, so there are uncountably many languages not in P. This result is, interestingly enough, independent of whether P = NP.
If you restrict "problems" to "decidable problems" (that is, problems that are solvable by computers with unbounded time and storage space), then we know that there are only countably many total decidable problems. Countably infinitely many of them are in P and, regardless of whether P = NP, there are countably infinitely many of them not in P.
Hope this helps!