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 1459
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.
5 votes
p\poly and NP definitions
A more illuminating way of thinking about P/poly than the definition you give is in terms of circuit complexity: in fact, P/poly is more like P than like NP (as its name suggests). It is an exercise …
- 29.4k
18 votes
Is P=NP relevant to finding proofs of everyday mathematical propositions?
I myself think that proving that P=NP is neither necessary nor sufficient for getting computers to solve mathematics problems. Not sufficient: it could produce long and virtually meaningless certifi …
- 29.4k
57 votes
Example of a good Zero Knowledge Proof
An example I like is this. I think I heard it from Avi Wigderson but I can't quite remember. (I don't know who actually thought of it.) You want to prove that a graph can be properly coloured with thr …
- 29.4k
0 votes
Is this a well known NP-complete problem?
The problem of finding the longest path in a graph is NP-complete. (See http://en.wikipedia.org/wiki/Longest_path_problem.) It follows that the problem of determining whether there exists a path of le …
- 29.4k
12 votes
The problem of finding the first digit in Graham's number
It seems to me that the question is really about the shortest proof that the first digit of Graham's number is what it is, rather than the shortest program that calculates it. Indeed, if you have an e …
- 29.4k
2 votes
Accepted
Boolean Cube of Primes
The argument that gives you cubes in dense sets shows roughly speaking (via repeated applications of Cauchy-Schwarz) that the number of k-dimensional cubes in a set of density delta is at least someth …
- 29.4k