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 7507
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.
11
votes
Accepted
Descriptive complexity theoretic-characterizations of P and NP
Remember that this is finite model theory and it is quite different from logic on infinite structures, e.g. satisfiability of first-order formulas on finite structures is $\Sigma_1$, whereas the same …
- 5,502
1
vote
Has Oracles actually provided intuition for proving anything in Complexity Theory?
IIRC, the circuit complexity classes like $\mathsf{AC^0}$ were studied originally for proving relativization results. A classical example is Furst, Saxe, and Sipser, "Parity, Circuits, and the Polynom …
- 5,502
0
votes
How small can a language in NP\P be?
To have a set $A\subseteq \{2\Uparrow n \mid n\in \mathbb N \}$ s.t. $A\in \mathsf{NP} -\mathsf{P}$, it suffices to have a set $A' \in \mathsf{NTime}(2\Uparrow n) - \mathsf{DTime}(2\Uparrow n)$ and l …
- 5,502
7
votes
Accepted
Oracle Results: P^A = NP^A
There is an oracle $A$ s.t. $\mathsf{P}^A = \mathsf{NP}^A$. The oracle normally used for the theorem is the set TQBF which is a $\mathsf{PSpace\text{-}complete}$ set.
$\mathsf{PSpace} \subseteq \math …
- 5,502
28
votes
2
answers
2k
views
Is there a syntactic characterization for BPP, BQP, or QMA?
Background
The complexity classes BPP, BQP, and QMA are defined semantically. Let me try to explain a little bit what is the difference between a semantic definition and a syntactic one. The complexi …
- 5,502
2
votes
Completeness, easiest, hardest problems
If you are looking for a complexity theoretic version of Rice's theorem, take a look at this old nice paper of Kozen:
Dexter Kozen, "Indexings of subrecursive classes", Theoretical Computer Science V …
- 5,502
3
votes
Most 'obvious' open problems in complexity theory
$AC^0[6] vs. NP$
In other words, it is open whether $SAT$ has polynomial size constant depth circuits using gates $\land$, $\lor$, $\lnot$, $mod_6$.
I think it is more than obvious, it is kind of e …
3
votes
Formal verification in complexity theory
Generally complexity theorist prefer to use as little formalism as possible. $\mathsf{IP}=\mathsf{PSpace}$ is on the list here but it doesn't seem that it has been verified with a proof assistant.
I …
- 5,502
3
votes
A programming language that can only create algorithms with polynomial runtime?
Yet another perspective (and IMHO a more natural one) is descriptive complexity theory (check also this Wikipedia article).
They study the question from a perspective different from the one mentione …
- 5,502
5
votes
Accepted
$\mu$-recursive definitions for the complexity classes P, NP, etc
Yes, there is. See [Cob64].
The idea is to replace primitive recursion
in the definition of primitive recursive functions with bounded recursion on notion.
Another more delicate approach is taken i …
- 5,502
15
votes
0
answers
1k
views
Razborov's response to Almost Natural Proofs
This post is about Natural Proofs barrier in computational complexity.
There are two recent papers related to this. They are:
Amplifying lower bounds by means of self-reducibility by Eric Allender …
- 5,502
13
votes
0
answers
2k
views
How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural pro...
EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.
Here are Vinay Deolalikar's paper, and Richard Lipton's first post ab …
- 5,502
16
votes
5
answers
4k
views
What are the most important results (and papers) in complexity theory that every one should ...
A few years ago Lance Fortnow listed his favorite theorems in complexity theory:
(1965-1974)
(1975-1984)
(1985-1994)
(1995-2004)
But he restricted himself (check the third one) and his last post is no …
4
votes
Lower Bounds in Theoretical Computer Science
There are a number of lowerbounds in circuit complexity.
Some well-known examples:
Parity is not in $AC^0$:
$mod_p$ is not in $AC^0[q]$.
k-Clique is not in $AC^0$.
There are also results for mono …
6
votes
Proof systems and their hierarchy
It is an open problem if there is an optimal propositional proof system. Therefore we don't know if ZFC as a propositional proof system is optimal either.
ZFC as propositional proof system can p-simu …
- 5,502