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 |
P versus NP and other resource-bounded computation.
5
votes
1
answer
263
views
Is there a fine grained relation between LH and AC0?
The wikipedia article states that the Logarithmic time hierarchy (LH) is equal to FO-uniform AC0. But since the natural way to think about LH is in terms of its levels (with DLogTime at the zeroth lev …
2
votes
Accepted
Relativized world where $L^A=NP^A$
My question is just whether there is a known relativization barrier.
Yes, there is a known relativization barrier. It's given by $A:=TQBF$, because Emil Jeřábek (see comments) is right: the state …
9
votes
Accepted
Is the finite inverse semigroup isomorphism problem GI-complete?
Yes, the finite inverse semigroup isomorphism problem is GI-complete! This is a corollary of
Theorem: Lattice isomorphism is isomorphism complete
from section 7.2 Lattices and Posets in
Boot …
4
votes
0
answers
193
views
Can coNLogTime verification be used instead of PTime verification when characterising NP?
I recently read a paper that presented a proof calculus where the verification of whether a given proof is valid was NL-complete. The authors apparently decided that the checking procedure was not loc …
2
votes
0
answers
114
views
Is equivalence of uniform AC0 decidable?
Is there a representation of the functions from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ for which equivalence is decidable?
Since the languages defined by nondeterministic pushdown automata belon …
0
votes
0
answers
102
views
Useful primitives CPUs could provide, from TC0 (or NC1)
I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational primitives …
11
votes
1
answer
317
views
Is the finite inverse semigroup isomorphism problem GI-complete?
Is the finite inverse semigroup isomorphism problem GI-complete? Here the finite inverse semigroups are assumed to be given by their multiplication tables.
5
votes
1
answer
383
views
Relativized world where $L^A=NP^A$
I wonder1 whether there is a known relativization barrier against proving $L\neq NP$. Hence I'm looking for a language $A$ for which $L^A=NP^A$.
My first idea was to try $A:=SAT$, but then I thought …
13
votes
1
answer
255
views
Conclusions from reverse mathematical strength of graph minor theorem
Say we have a graph property which can be checked in nondeterministic polynomial time, and a proof in a weak formal system (say RCA0) that the property is minor closed. Can we say anything about the s …
16
votes
Accepted
What evidence is there that Graph Isomorphism is not in $P$?
Before this question, my opinion was that Graph Isomorphism might be in P, i.e. that there is no evidence to believe that GI is not in P. So I asked myself what would count as evidence for me: If ther …
0
votes
Limits to Parallel Computing
I answered the similar question Are there any famous problems/algorithms in scientific computing that cannot be sped up by parallelisation on the Computational Science site. Let me quote it here, beca …
0
votes
Reasons to believe $P \ne NP \cap coNP$ (or not)
I believe that there exists very space efficient high quality random number generators. Despite this belief, I normally use Mersenne twister in my code, which is high quality, but not very space effic …
5
votes
Reasons to believe $P \ne NP \cap coNP$ (or not)
Theorem 3.1 of One-Way Permutations and Self-Witnessing Languages C. Homan and M. Thakur, Journal of Computer and System Sciences, 67(3):608-622, November 2003. [ as .pdf ] states that $P≠UP∩coUP$ if …
3
votes
The unreasonable power of non-uniformity
I have the impression that the real issue here is the unreasonable heavy burden of proof, not the unreasonable power of non-uniformity. As the answers by chazisop and András Salamon already stress, un …
2
votes
Is there a theory that combines category theory/abstract algebra and computational complexity?
This answer about isomorphisms between formal languages combines algebraic results from the theory of codes with notions from category theory to investigate possible notions of equivalence and isomorp …