Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author | user:1234 user:me (yours) |
| Score | score:3 (3+) score:0 (none) |
| Answers | answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections | title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status | closed:yes duplicate:no migrated:no wiki:no |
| Types | is:question is:answer |
| Exclude | -[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computational-complexity
Search options answers only not deleted user 1946
This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Kolmogorov Complexity and so on.
6 votes
Does IP = PSPACE work over other rings?
First, it seems clear that there are at least some rings with your property, since the case of $Z_3$ or any other finite ring corresponds to simply having a larger finite alphabet, which would amount …
- 246k
7 votes
Correct to characterise NP set as P-time image of P set?
Every NP set is realized that way. And the characterization is correct in both directions if you add the stipulation that $f(b)$ and $b$ are polynomially related in size. First, every NP set is a p …
- 246k
12 votes
Accepted
Growth of Functions
The answer is no. By (1), we know that $f(f(n))\leq k f(n)$ for some constant $k$ and sufficiently large $n$. By (2), we get in particular that $c n^2\leq f(n)$ for some constant $c$ and sufficiently …
- 246k
4 votes
Oracle Separation Survey
The Complexity Zoo compiles a huge amount of the information you want, if not exactly in the form you request.
- 246k
5 votes
How small can a language in NP\P be?
This doesn't specifically address (1) or (2), but let me instead try to answer the title question of how small a set in NP-P can be. Definition. The asymptotic density of a language $L$, a set of str …
- 246k
10 votes
Accepted
shallow question: Why a 300 digit number is associated with "any NP-hard problem"?
Euclid's algorithm for computing the GCD of two numbers is linear time computable in the number of digits in each of the two numbers. Meanwhile, it is known by the time hierarchy theorems that there a …
- 246k
3 votes
Accepted
Constructing Useful SAT Instances
Every such set of strings determines a collection of rows in the truth table, and so you want an expression that is logically equivalent to the disjunction of those rows. This gives a logical expressi …
- 246k
5 votes
Accepted
are all NP problems made up of P problems?
The answer is yes. Suppose that $A$ is any NP problem, so there is a polynomial time algorithm $p$ such that $a\in A$ just in case there is some $b$ (of size at most $q(|a|)$, where $q$ is a fixed po …
- 246k
6 votes
nonasymptotic complexity results
The general fact surrounding some of the other answers is the following: Every computably axiomatizable consistent theory $T$ containing trivial arithmetic admits very short theorems requiring extrem …
- 246k
2 votes
Length preserving rewriting system with NP-complete $u\to v$ problem
It seems to me that the solution I posted at the other question (to which you link) provides an answer also to this question. Simply let $e$ be a program solving a fixed NP-complete problem, and let …
- 246k
9 votes
Accepted
Computational complexity of the word problem for semi-Thue systems with certain restrictions
The problem is at least NP-hard. Indeed, it is at least PSPACE-hard. The reason the original semi-Thue rewrite system is undecidable is that it reduces the halting problem. Given any Turing machine p …
- 246k
23 votes
How many Complexity Classes do you know?
See the Complexity Zoo, which seems to aim at being current. It currently lists 495 classes, including PPAD, as you mention, and a large diagram of some of the classes.
- 246k
15 votes
Accepted
Are there complexity classes with provably no complete problems?
The zoo of complexity classes extends naturally into the realm of computability theory and beyond, to descriptive set theory, and in these higher realms there are numerous natural classes which have …
- 246k
7 votes
Completeness, easiest, hardest problems
One of the most common and powerful means of showing that a decision problem is undecidable is, as in the case you mention, to show that the halting problem reduces to it. For example, this is the bas …
- 246k
5 votes
Are there any pairing functions computable in constant time (AC⁰)
The pairing function f(a,b) = (a + b)(a + b + 1)/2 + a is the one that arises by drawing diagonals on the natural number lattice, and marching down them from upper left to lower right. See the picture …
- 246k