ShyPerson's user avatar
ShyPerson's user avatar
ShyPerson's user avatar
ShyPerson
  • Member for 11 years, 11 months
  • Last seen this week
4 votes
1 answer
1k views

Resolution complexity versus a constrained SAT algorithm

6 votes
1 answer
968 views

Generalizing the Comparison Sorting Lower Bound Proof

13 votes
1 answer
531 views

Restricted version of the Clique problem?

2 votes
3 answers
299 views

Search spaces and computation time

2 votes
0 answers
226 views

State of the Art in linear-time DFA minimization

1 vote
1 answer
197 views

Details wanted on the reduction from Circuit Value to CFG Membership

5 votes
1 answer
196 views

Maximal minimal DFA for some language of n-bit strings

0 votes
2 answers
182 views

Cliques in an alternate graph representation

0 votes
0 answers
182 views

Program to Translate Turing Machine to Tableau?

4 votes
1 answer
125 views

Proofs based on narrowing down sets of possibilities

1 vote
1 answer
109 views

Comparing automata sizes given Myhill-Nerode equivalence under a function

2 votes
2 answers
91 views

Counting States in the trim automaton for $L\circ L'$

1 vote
1 answer
86 views

Myhill-Nerode equivalence under a function

1 vote
1 answer
84 views

Progress of algorithms in problem spaces

0 votes
0 answers
82 views

Multiple loops in a Turing Machine?

1 vote
1 answer
82 views

State Complexity of DFAs for Restricted Languages

2 votes
0 answers
80 views

Minimization of simple cyclic automata

1 vote
1 answer
75 views

Relationship between circuit size and formula size in Sipser text

1 vote
1 answer
72 views

Complexity of negation cancellation

0 votes
0 answers
69 views

Existence of a loop in a Turing machine?

2 votes
1 answer
56 views

Circuits and formulas for Clique

1 vote
0 answers
48 views

Best-known Boolean Circuits for Clique? [closed]

0 votes
1 answer
45 views

Algorithms that must compute a global property?

1 vote
1 answer
40 views

Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$

1 vote
1 answer
39 views

Complexity of a Set of Formulas

0 votes
1 answer
38 views

How big is a formula equivalent to a wff over $n$ variables with $2^n$ subformulas?

0 votes
0 answers
37 views

Growth of a set of propositional formulas under partial evaluation

0 votes
1 answer
33 views

Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$