vzn
  • Member for 10 years
  • Last seen more than a month ago
2 answers
16 votes
5k views
5 bookmarks
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
3 answers
27 votes
3k views
17 bookmarks
Impact of Grothendieck's program on TCS
2 answers
21 votes
3k views
9 bookmarks
computing the minimal NFA for a DFA
1 answers
-5 votes
1k views
1 bookmarks
why is a Turing machine defined as a 5-tuple?
2 answers
8 votes
1k views
3 bookmarks
(0,1)-vector XOR problem
1 answers
3 votes
1k views
1 bookmarks
What NP-complete problems are most similar to integer factoring?
2 answers
9 votes
1k views
4 bookmarks
Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?
2 answers
8 votes
1k views
4 bookmarks
Automated theorem proving via unsupervised approaches
0 answers
6 votes
944 views
5 bookmarks
k-CNF ←→ k-DNF conversion to minimize errors
4 answers
2 votes
884 views
3 bookmarks
Turing-complete computation models on graphs
2 answers
9 votes
843 views
5 bookmarks
Is adiabatic quantum computing as powerful as the circuit model?
2 answers
11 votes
841 views
2 bookmarks
What's the correlation between treewidth and instance hardness for random 3-SAT?
2 answers
10 votes
841 views
3 bookmarks
Implications of Riemann Hypothesis variants in TCS
1 answers
12 votes
811 views
1 bookmarks
L/P/PSpace vs P/NP
1 answers
1 votes
721 views
1 bookmarks
finding "hubs" in a graph
2 answers
-9 votes
678 views
Is every "nontrivial" algorithm Turing-complete?
2 answers
0 votes
632 views
1 bookmarks
largest language class for which inclusion is decidable
1 answers
11 votes
632 views
2 bookmarks
What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?
1 answers
8 votes
595 views
2 bookmarks
Connections between the Erdos Discrepancy Problem and (Theoretical) CS?
3 answers
4 votes
580 views
3 bookmarks
How to minimize a FSM transducer?
1 answers
1 votes
574 views
2 bookmarks
equivalent way(s) of expressing P=?NP problem in linear programming?
1 answers
2 votes
550 views
1 bookmarks
techniques or examples of analyzing a series of graphs
0 answers
11 votes
525 views
2 bookmarks
Has there been any result which does not have any Natural Proofs?
2 answers
4 votes
506 views
1 bookmarks
P/poly vs NP separation based on circuit trees instead of DAGs
1 answers
8 votes
477 views
2 bookmarks
Are there applications of modular graph decomposition in TCS/complexity theory?
1 answers
-4 votes
467 views
1 bookmarks
"tree-like" vs "DAG-like" resolution
2 answers
3 votes
444 views
1 bookmarks
Factoring Cartesian bitwise join of bit vectors
1 answers
4 votes
413 views
2 bookmarks
Analogies between VNP and NP
4 answers
5 votes
406 views
3 bookmarks
What is some important work in fractals?
2 answers
7 votes
392 views
1 bookmarks
possible bridge between group growth theory and complexity theory?