vzn
  • Member for 10 years
  • Last seen more than a month ago
2 answers
-9 votes
678 views
Is every "nontrivial" algorithm Turing-complete?
2 answers
21 votes
3k views
9 bookmarks
computing the minimal NFA for a DFA
1 answers
3 votes
222 views
2 bookmarks
Finding self-similar homomorphisms of a FSM transducer
0 answers
5 votes
284 views
2 bookmarks
Sketch of Razborov's paper "On the method of approximations"
1 answers
1 votes
574 views
2 bookmarks
equivalent way(s) of expressing P=?NP problem in linear programming?
2 answers
7 votes
392 views
1 bookmarks
possible bridge between group growth theory and complexity theory?
1 answers
-2 votes
239 views
questions on implications Babais quasi P time graph isomorphism result
1 answers
8 votes
294 views
4 bookmarks
Two DFA intersection emptiness connections to SETH & L vs P
2 answers
6 votes
258 views
1 bookmarks
FSM transducer sequential composition decidability
1 answers
10 votes
246 views
1 bookmarks
Is it decidable whether the output length of a transducer is bounded by the input length?
2 answers
10 votes
274 views
2 bookmarks
Matrix vector multiplication algorithm using minimal number of additions
1 answers
12 votes
811 views
1 bookmarks
L/P/PSpace vs P/NP
1 answers
-2 votes
122 views
what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?
2 answers
16 votes
5k views
5 bookmarks
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
1 answers
4 votes
413 views
2 bookmarks
Analogies between VNP and NP
0 answers
1 votes
72 views
complexity of factoring multivariate polynomials over Fn
2 answers
1 votes
217 views
1 bookmarks
research on systematically attacking multiple instances of undecidable problems
2 answers
3 votes
245 views
computing maximal bit density over a FSM
1 answers
4 votes
283 views
minimal finite automata given in-words and out-words
2 answers
10 votes
841 views
3 bookmarks
Implications of Riemann Hypothesis variants in TCS
3 answers
27 votes
3k views
17 bookmarks
Impact of Grothendieck's program on TCS
0 answers
1 votes
341 views
intuition that VP=?VNP is (not?) connected to P=?NP
2 answers
11 votes
841 views
2 bookmarks
What's the correlation between treewidth and instance hardness for random 3-SAT?
2 answers
8 votes
1k views
4 bookmarks
Automated theorem proving via unsupervised approaches
0 answers
2 votes
170 views
2 bookmarks
proving speedup phenomenon does not apply to any open complexity class separations
0 answers
5 votes
119 views
2 bookmarks
extracting/ exploiting similarity of SAT instances by solver
0 answers
3 votes
125 views
2 bookmarks
minimal languages that "cover" grammar productions
1 answers
5 votes
295 views
3 bookmarks
any relation/ overlap between small world graphs, scale free graphs, and expander graphs?
2 answers
4 votes
364 views
2 bookmarks
TCS oriented refs/survey on group theoretic word problem
1 answers
0 votes
326 views
1 bookmarks
is determining an unknown CFL from intersection of two CFLs decidable?