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"
Bookmarks inbookmarks:mine
inbookmarks:1234
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
Search options user 40

Computational complexity classes and their relations

6
votes
Given a Turing machine $T$ and an a number $n$ encoded in unary, decide whether $T$ halts in time $2^n$. There is an $O(C^n)$ algorithm for this, and there's an almost matching $\Omega(c^n)$ lower bou …
answered Jan 17 '15 by Yuval Filmus
4
votes
Perhaps you'd be interested in switching networks. According to Potechin's Bounds on monotone switching networks for directed connectivity, one way to separate L from NL is to show that there is no po …
answered Sep 4 '12 by Yuval Filmus
13
votes
Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects …
answered Sep 1 '17 by Yuval Filmus
8
votes
It is clear that your language is in DP. In order to show that it is DP-hard, we will give a reduction from SAT-UNSAT to your language, which we can call CRIT-UNSAT. Given a pair of CNFs $(f,g)$, let …
answered Jul 31 '17 by Yuval Filmus
7
votes
You can use the usual switching lemma argument. You haven't explained how you represent your input in binary, but under any reasonable encoding, the following function is AC$^0$-equivalent to your fun …
answered Oct 31 '13 by Yuval Filmus
8
votes
The other two "classical" methods are Haken's bottleneck method and Karchmer's fusion method (so named by Avi Wigderson), both much easier to apply in the monotone setting.
answered Nov 20 '10 by Yuval Filmus