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 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; Komolgorov Complexity and so on.
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 …
- 236k
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 …
- 236k
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 …
- 236k
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 …
- 236k
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 …
- 236k
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 …
- 236k
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.
- 236k
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 …
- 236k
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 …
- 236k
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 …
- 236k
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 …
- 236k
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.
- 236k
14
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 …
- 236k
5
votes
Accepted
Turing and Many one reductions in computability versus complexity
The basic reductions in computability theory are:
A set $A$ is Turing reducible to $B$, if there is a computable
procedure that can correctly answer queries about $A$ using an
oracle for $B$.
A set …
- 236k
5
votes
The relationship between P vs NP problem and "Kolmogorov complexity with time"
Let's assume that Mark's description of the problem in the comments is correct, so that we have a fixed polynomial $P$, and the decision problem is: given $l$ and $n$, such that $l\lt \log(n)$, decide …
- 236k