Skip to main content
ShyPerson's user avatar
ShyPerson's user avatar
ShyPerson's user avatar
ShyPerson
  • Member for 13 years, 9 months
  • Last seen more than a week ago
6 votes
3 answers
528 views

Information-theoretic proof of Gödel's Theorem?

6 votes
1 answer
736 views

Has the Four-Color Theorem been accepted?

5 votes
2 answers
458 views

Question about the P versus NP Problem

4 votes
1 answer
867 views

Practice Problems on the Elimination of Quantifiers

4 votes
1 answer
217 views

Gradualness of Polynomial-time Recognizers

3 votes
1 answer
118 views

Treatments of Mahaney's Theorem?

2 votes
0 answers
39 views

Tutorials on lexicographically first maximal clique?

2 votes
1 answer
106 views

Best-known Boolean Circuits for Clique?

2 votes
1 answer
107 views

Axioms of Propositional Logic with as few negation axioms as possible

2 votes
1 answer
572 views

Negation Normal Form and the length of formulas

2 votes
1 answer
923 views

Right-moving Turing Machines

2 votes
0 answers
57 views

How many implication graphs are there for a given number of literals?

2 votes
2 answers
90 views

Will an optimal algorithm halt when it has read enough of the input to generate a correct answer?

2 votes
1 answer
67 views

How big is the result when reducing from Clique to an NP-Complete sparse language and back again?

1 vote
0 answers
39 views

P versus NP and the Irreducibility of NP-Complete Problems to P-Complete Problems

1 vote
1 answer
132 views

Growth of Complete Binary Decision Trees

1 vote
1 answer
57 views

Can this disjunction be eliminated?

1 vote
2 answers
150 views

Survey Article on Decision Tree Proofs

1 vote
1 answer
81 views

Negation normal form with cancellations barred

1 vote
1 answer
70 views

Cancellation of negations and the length of formulas

1 vote
1 answer
129 views

Axiomatization of field theory for the Knuth-Bendix algorithm?

1 vote
0 answers
96 views

Scott Aaronson tests for faulty P $\neq$ NP proofs; separating 2-SAT

1 vote
1 answer
78 views

Counting cliques in a graph asymptotically

0 votes
0 answers
43 views

Halting behavior of optimal algorithms on getting enough input