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 2294
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
Is there an interactive proof system for factoring with the perfect zero knowledge property?
If by the decision version of the factoring problem you mean: does this number have a non-trivial factorization (i.e. is this number prime?), that's primality testing, which is in P so it's automatica …
- 6,332
10
votes
Accepted
An Alternative to the Cook-Levin Theorem
In his infamously short paper "Average-case complete problems," Leonid Levin uses a tiling problem as the master ("first") NP-complete average-case problem (which means he also automatically uses it a …
- 6,332
10
votes
How do you handle numerical issues when converting optimization problems to decision problems?
For most NP-complete problems, you can without loss of generality work with rational numbers, in which case you don't run into issues of precision. There are a few problems which do run into difficult …
- 6,332
28
votes
Accepted
Is #k-XORSAT #P-complete?
The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem …
- 6,332
10
votes
Accepted
Does NP = "epsilon-P" (PTAS / BPP)?
The answer to this question is essentially given in previous answers, but I'll try to state it more completely. It really depends on the problem. All NP-complete problems are equivalent in how hard it …
- 6,332
13
votes
Most 'obvious' open problems in complexity theory
In 1990, my intuition (and I don't think it was just mine) was that IP couldn't possibly contain PSPACE. Intuition was wrong.
18
votes
Accepted
Why do statistical randomness tests seem so ad hoc?
It's not clear that Marsaglia's tests are really good enough. See this Stack Overflow discussion.
Kolmogorov complexity is not the right criterion for statistical randomness tests, since any pseudora …
- 6,332
22
votes
Accepted
Complete problems for randomized complexity classes
In general, for randomized classes complete problems tend to be either promise problems or approximation problems (which means they don't technically satisfy the conditions for being complete problems …
- 6,332
2
votes
Drawing 3-configurations of points and lines with straight lines
Let's try this again. If there weren't a degree constraint on the graph, then you could adapt the proof of Mnev's universality theorem (see my previous answer) to show that the problem was equivalent …
- 6,332
5
votes
Drawing 3-configurations of points and lines with straight lines
Ten minutes ago I gave the wrong answer. I said:
"You haven't mentioned Mnev's universality theorem, so I'll assume you don't know about it. Bokowski and Sturmfels is too old to refer to it, and for s …
- 6,332
29
votes
Problems known to be in both NP and coNP, but not known to be in P
One of my favorite problems in NP $\cap$ co-NP is deciding who wins a simple stochastic game. The game is played on a directed graph by two players, call them A and B. This graph contains several type …
15
votes
Accepted
Are there any known quantum algorithms that clearly fall outside a few narrow classes?
Does the Farhi-Goldstone-Gutman game tree evaluation algorithm and the extensions of it fall into one of these classes? You might put it in quantum simulation/annealing because of the technique used, …
- 6,332