Skip to main content
diplodocus's user avatar
diplodocus's user avatar
diplodocus's user avatar
diplodocus
  • Member for 4 years, 11 months
  • Last seen more than a month ago
1 vote

If a sparse language is NP complete, then are all languages in NP in P/poly?

0 votes

Finding the hidden treasure

2 votes

BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$

1 vote

Rice Theorem - Problem to understand and apply it

3 votes

Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?

2 votes

The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6)

1 vote
Accepted

Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang)

1 vote

Complexity guess and induction proof

1 vote
Accepted

TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?

0 votes

Converting a Recurrence Relation to its Closed Form

2 votes

Karatsuba Multiplication Rule in dividing a Number in two parts

0 votes

How Reduction works in proving NP-Hard?