user avatar
user avatar
user avatar
Ludovic Patey
  • Member for 11 years, 10 months
  • Last seen more than 5 years ago
30 votes
1 answer
1k views

Are there canonical non-relativizing techniques?

30 votes
3 answers
2k views

Justification of log f in DTIME hierarchy theorem

12 votes
4 answers
903 views

Does diagonalization captures the essence of class separation ?

12 votes
2 answers
255 views

Reducing threshold questions to finiteness questions

11 votes
6 answers
2k views

Do many-one reductions and Turing reductions define the same class NPC

10 votes
1 answer
431 views

What are the complexities of the following SAT subsets ?

10 votes
1 answer
431 views

Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ?

9 votes
1 answer
827 views

Literature around NP vs EXPTIME

6 votes
1 answer
371 views

$\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$

6 votes
5 answers
3k views

Sorting algorithm with a complexity smaller than $n \log n$?

5 votes
1 answer
278 views

Are there known "completion" operations over languages ?

1 vote
2 answers
446 views

Shouldn't relativisation contain consistency proof ?

0 votes
2 answers
923 views

Where is the error in the following P != NP pseudo-proof ?