Tayfun Pay
  • Member for 11 years, 3 months
  • Last seen more than a month ago
4 answers
23 votes
1k views
8 bookmarks
Survey on #P and/or counting problems
4 answers
18 votes
2k views
6 bookmarks
List of theorems stating that P does not equal NP if and only if
1 answers
14 votes
747 views
3 bookmarks
Is Quasi-polynomial time in PSPACE?
2 answers
13 votes
2k views
4 bookmarks
What is the precise definition of Random K-SAT?
1 answers
11 votes
1k views
5 bookmarks
What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?
1 answers
11 votes
440 views
Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
1 answers
11 votes
575 views
What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?
1 answers
11 votes
674 views
Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$
1 answers
11 votes
401 views
1 bookmarks
What do we know about the phase transition of #P-Complete problems?
5 answers
8 votes
943 views
A problem that is in PSPACE but not known to be in PH?
3 answers
7 votes
564 views
2 bookmarks
Does there exist a complexity class such that the number of accepting paths is a prime number?
3 answers
6 votes
391 views
Are there any natural hard problems where it is required that the number of solutions are always more than one?
1 answers
5 votes
214 views
3 bookmarks
Eliminating clauses from a CNF formula based on their unsatisfying truth assignments being covered by some other clause
1 answers
4 votes
302 views
Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P
1 answers
1 votes
579 views
Karp-like reductions vs Cook-like reductions for Functional Complexity Classes.
1 answers
1 votes
233 views
1 bookmarks
Complexity of a certain leaf language with Prime & Composite number of accepting paths.
1 answers
-2 votes
951 views
Are all complexity classes closed under a particular reduction?