user avatar
user avatar
user avatar
Tayfun Pay
  • Member for 11 years, 9 months
  • Last seen more than a week ago
15 votes

Counting the number of satisfying assignments in a POSITIVE CNF-SAT

12 votes

Consequences of NP=PSPACE

8 votes

Most memorable CS paper titles

8 votes

Major unsolved problems in theoretical computer science?

7 votes

Consequences of $NP=coNP$ and $P\ne NP$?

7 votes

When does "X is NP-complete" imply "#X is #P-complete"?

6 votes
Accepted

${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

6 votes

Papers every complexity theorist should read

6 votes

Do we know whether P^#P = NP^#P?

5 votes
Accepted

What is the computational complexity of this SAT Variant

5 votes
Accepted

Composition of $FP$ and $\#P$ functions

4 votes

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

4 votes
Accepted

$FNP$ ,$ \#P$,$\oplus P$ classes

3 votes

How can I show a Gap-P problem is outside #P

2 votes

What hierarchies and/or hierarchy theorems do you know?

2 votes

What CS theories are absolutely paramount for someone new to TCS to understand?

1 vote
Accepted

A problem that is in PSPACE but not known to be in PH?

0 votes

Benefits for syntactic and semantic classes