Skip to main content
vzn's user avatar
vzn's user avatar
vzn's user avatar
vzn
  • Member for 12 years, 5 months
  • Last seen more than 3 years ago
19 votes
2 answers
6k views

What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

23 votes
2 answers
4k views

computing the minimal NFA for a DFA

28 votes
3 answers
4k views

Impact of Grothendieck's program on TCS

-5 votes
1 answer
2k views

why is a Turing machine defined as a 5-tuple? [closed]

3 votes
1 answer
2k views

What NP-complete problems are most similar to integer factoring?

9 votes
2 answers
2k views

(0,1)-vector XOR problem

8 votes
2 answers
1k views

Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

3 votes
4 answers
1k views

Turing-complete computation models on graphs

9 votes
2 answers
1k views

Automated theorem proving via unsupervised approaches

6 votes
0 answers
1k views

k-CNF ←→ k-DNF conversion to minimize errors

1 vote
1 answer
1k views

finding "hubs" in a graph

12 votes
1 answer
990 views

L/P/PSpace vs P/NP

13 votes
2 answers
941 views

What's the correlation between treewidth and instance hardness for random 3-SAT?

9 votes
2 answers
890 views

Implications of Riemann Hypothesis variants in TCS

9 votes
2 answers
864 views

Is adiabatic quantum computing as powerful as the circuit model?

12 votes
1 answer
774 views

What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

4 votes
3 answers
722 views

How to minimize a FSM transducer?

-9 votes
2 answers
697 views

Is every "nontrivial" algorithm Turing-complete?

0 votes
2 answers
685 views

largest language class for which inclusion is decidable

1 vote
1 answer
628 views

equivalent way(s) of expressing P=?NP problem in linear programming?

8 votes
1 answer
604 views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

-4 votes
1 answer
585 views

"tree-like" vs "DAG-like" resolution

2 votes
1 answer
575 views

techniques or examples of analyzing a series of graphs

4 votes
2 answers
557 views

P/poly vs NP separation based on circuit trees instead of DAGs

11 votes
0 answers
542 views

Has there been any result which does not have any Natural Proofs?

8 votes
1 answer
498 views

Are there applications of modular graph decomposition in TCS/complexity theory?

3 votes
2 answers
477 views

Factoring Cartesian bitwise join of bit vectors

4 votes
1 answer
459 views

Analogies between VNP and NP

1 vote
0 answers
421 views

intuition that VP=?VNP is (not?) connected to P=?NP

5 votes
4 answers
413 views

What is some important work in fractals?