Tour
About Us
Meta
Loading…
Log in
current community
Stack Exchange
chat
Meta Stack Exchange
your communities
Sign up
or
log in
to customize your list.
more stack exchange communities
company blog
Stack Exchange
All Sites
Top Users
Digests
Andras Farago
Richardson, Texas (suburb of Dallas)
http://www.utdallas.edu/~farago
top
accounts
reputation
activity
bookmarks
subscriptions
Top Questions
54
votes
For which problems in P is it easier to verify the result than to find it?
cc.complexity-theory
ds.algorithms
reference-request
asked Oct 31 '15 at 14:56
cstheory.stackexchange.com
45
votes
Obituaries of dead conjectures
cc.complexity-theory
ds.algorithms
asked Oct 5 '15 at 20:37
cstheory.stackexchange.com
38
votes
Examples where the uniqueness of the solution makes it easier to find
cc.complexity-theory
ds.algorithms
graph-algorithms
complexity-classes
unique-solution
asked Apr 12 '14 at 16:00
cstheory.stackexchange.com
36
votes
Why does randomness have stronger effect on reductions than on algorithms?
cc.complexity-theory
reductions
derandomization
asked Dec 21 '12 at 19:18
cstheory.stackexchange.com
36
votes
Hardness of approximation without the PCP theorem
cc.complexity-theory
approximation-hardness
pcp
asked Dec 2 '12 at 4:19
cstheory.stackexchange.com
34
votes
Hardest known natural problem in P?
cc.complexity-theory
ds.algorithms
asked Jan 9 '14 at 18:18
cstheory.stackexchange.com
33
votes
The unreasonable power of non-uniformity
cc.complexity-theory
complexity-classes
big-picture
asked Apr 30 '14 at 2:15
cstheory.stackexchange.com
31
votes
Why are so few natural candidates for NP-intermediate status?
cc.complexity-theory
p-vs-np
np-intermediate
asked Feb 7 '14 at 22:59
cstheory.stackexchange.com
29
votes
Hard-looking algorithmic problems made easy by theorems
cc.complexity-theory
ds.algorithms
graph-algorithms
asked Feb 13 '14 at 0:52
cstheory.stackexchange.com
26
votes
Is there an NP-complete language that contains precisely half of the n-bit instances?
cc.complexity-theory
np
np-complete
asked Nov 25 '16 at 15:12
cstheory.stackexchange.com
1
2
3
4
5
next
Top Answers
21
Is NP in $DTIME(n^{poly\log n})$?
cstheory.stackexchange.com
19
Which randomized algorithms have exponentially small error probability?
cstheory.stackexchange.com
15
Easy to optimize but hard to evaluate
cstheory.stackexchange.com
12
Consequences of $NP=coNP$ and $P\ne NP$?
cstheory.stackexchange.com
12
Problems that are easy on unweighted graphs, but hard for weighted graphs
cstheory.stackexchange.com
11
Evidence that Graph Isomorphism problem is not $NP$-complete
cstheory.stackexchange.com
8
Natural NP-complete problems with “large” witnesses
cstheory.stackexchange.com
8
Complexity of finding an edge set yielding specified vertex degrees
cstheory.stackexchange.com
7
Natural graphs that are not scale free
cstheory.stackexchange.com
7
Completeness under injective Karp reductions
cstheory.stackexchange.com
5
Hard-looking algorithmic problems made easy by theorems
cstheory.stackexchange.com
5
A curious asymmetry in good characterizations
cstheory.stackexchange.com
5
“Almost easy” NP-complete problems
cstheory.stackexchange.com
5
Examples of the value of proofs for algorithms
cstheory.stackexchange.com
Stack Exchange works best with JavaScript enabled