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
4 votes
2 answers
374 views

TCS oriented refs/survey on group theoretic word problem

4 votes
1 answer
459 views

Analogies between VNP and NP

4 votes
1 answer
318 views

minimal finite automata given in-words and out-words

3 votes
2 answers
249 views

computing maximal bit density over a FSM

3 votes
4 answers
1k views

Turing-complete computation models on graphs

3 votes
0 answers
131 views

minimal languages that "cover" grammar productions

3 votes
1 answer
236 views

Finding self-similar homomorphisms of a FSM transducer

3 votes
1 answer
2k views

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

3 votes
2 answers
477 views

Factoring Cartesian bitwise join of bit vectors

2 votes
1 answer
575 views

techniques or examples of analyzing a series of graphs

2 votes
0 answers
183 views

proving speedup phenomenon does not apply to any open complexity class separations

1 vote
0 answers
421 views

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

1 vote
0 answers
146 views

looking for notable applications of ASP (Answer Set Programming) in TCS

1 vote
0 answers
76 views

complexity of factoring multivariate polynomials over Fn

1 vote
1 answer
336 views

in SAT resolution proofs, are all DAGs possible? [closed]

1 vote
1 answer
397 views

Questions about computing matrix rigidity

1 vote
2 answers
224 views

research on systematically attacking multiple instances of undecidable problems

1 vote
1 answer
1k views

finding "hubs" in a graph

1 vote
1 answer
628 views

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

0 votes
2 answers
685 views

largest language class for which inclusion is decidable

0 votes
2 answers
183 views

iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

0 votes
1 answer
377 views

is determining an unknown CFL from intersection of two CFLs decidable?

-2 votes
1 answer
128 views

what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?

-2 votes
1 answer
269 views

questions on implications Babais quasi P time graph isomorphism result

-3 votes
1 answer
174 views

computing with gates on polar coordinates, functionally complete wrt boolean functions?

-4 votes
1 answer
585 views

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

-5 votes
1 answer
373 views

Attacking TSP via small nonintersecting circuits

-5 votes
1 answer
338 views

whats the difference between nondeterminism and parallelism? [closed]

-5 votes
1 answer
2k views

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

-9 votes
2 answers
697 views

Is every "nontrivial" algorithm Turing-complete?

1
2