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.
16
votes
Accepted
Non-constructive proofs vs. efficient algorithms
As others have noted there are several different meanings for constructive.
I. Constructive proof in the sense of constructive mathematics
This meaning views an object as existing if we have a descrip …
- 1,446
7
votes
Solving NP problems in (usually) Polynomial time?
Your post seems to assume something like $\mathsf{P} \neq \mathsf{NP}$ and that an $\mathsf{NP\text{-}complete}$ problem is difficult to solve at least in theory. As you are probably aware, although w …
CommunityBot
- 1
2
votes
How to define the input of computable function or Turing machine over real numbers
A good book on the complexity of real constants and functions is Ker-I Ko's "Computational Complexity of Real Functions", 1991.
- 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 …
CommunityBot
- 1
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
3
votes
0
answers
256
views
Oracle separating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on...
Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP?
Such an oracle …
CommunityBot
- 1
7
votes
0
answers
297
views
Feasible Type Theories
I am looking for references about efficient type theories,
efficiency in the sense of computational complexity,
and type theory in the sense of Martin-Lof's type theories.
Has there been any studies …
- 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
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
3
votes
Ordinals and complexity classes
You may want to check "Dynamic Ordinal Analysis" by Arnold Beckmann which is an attempt to define a finer notion to classical ordinals that can be used ti distinguish between complexity classes.
- 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
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
5
votes
Definition of relativization of complexity class
There isn't one correct definition of a relativization of a complexity class. Depending on the circumstances there are different definitions which are useful. So we don't have a single way of defining …
- 5,502
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
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 …
CommunityBot
- 1