User 1..

2

8

votes

3

answers

503

views

Simple interepretation problem regarding Polynomial Hierarchy?

complexity-theory np

Jul 16 '19 at 10:22 Thomas Klimpel 5,183

8

votes

2

answers

437

views

Software for testing graph homomorphism

complexity-theory graphs

Oct 25 '13 at 19:08 Community♦ 1

7

votes

1

answer

237

views

$\mathsf{PP=RP}$ consequences

complexity-theory complexity-classes

Nov 24 '16 at 14:44 Community♦ 1

3

7

votes

1

answer

169

views

Relativization results in class separation

complexity-theory

Apr 19 '15 at 9:42 Pål GD 9,451

3

7

votes

1

answer

707

views

Randomized and deterministic reduction

np-complete reductions

Jan 1 '15 at 11:21 1.. 2,692

2

6

votes

1

answer

409

views

On complete problems for $P/poly$ and $BPP$

complexity-theory

Oct 23 '16 at 23:02 Ariel 11.9k

5

votes

1

answer

229

views

If NP is a subset of DTIME[n^O(log n)] then what happens?

complexity-theory time-complexity np complexity-classes nondeterminism

Jan 2 '20 at 8:18 xskxzr 6,539

5

votes

1

answer

344

views

Adleman's theorem to $\mathsf{P=BPP}$

complexity-theory

Sep 19 '18 at 15:52 Community♦ 1

2

5

votes

2

answers

412

views

Why does this not prove $P\neq NP$?

complexity-theory proof-techniques linear-programming p-vs-np traveling-salesman

Aug 18 '17 at 12:18 Community♦ 1

2

5

votes

1

answer

176

views

Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?

complexity-theory circuits

Mar 22 '17 at 10:23 1.. 2,692

1

5

votes

2

answers

870

views

Sensitivity and Block sensitivity

complexity-theory boolean-algebra

Dec 5 '14 at 11:46 Raphael♦ 69.3k

5

votes

1

answer

50

views

Is complexity of $GI_{di}$ same as $GI_{un}$?

complexity-theory reductions graph-isomorphism

Nov 10 '14 at 12:31 Raphael♦ 69.3k

1

5

votes

1

answer

68

views

A containment result in complexity

complexity-theory

Sep 27 '13 at 21:52 Yuval Filmus 247k

5

votes

2

answers

2k

views

How does Grover's Quantum Sorting avoid reading the list?

algorithms sorting quantum-computing

Sep 22 '13 at 6:29 D.W.♦ 129k

5

votes

1

answer

227

views

Modulo operation in monotone complexity

complexity-theory circuits

Sep 18 '13 at 10:44 1.. 2,692

4

votes

1

answer

117

views

What is the consequence of $\oplus P\neq PP$?

complexity-theory complexity-classes

Aug 24 at 16:08 Community♦ 1

1

4

votes

2

answers

185

views

Does real linear programming produce bipartite perfect matching using maxflow reduction?

linear-programming network-flow integer-programming bipartite-matching bipartite-graph

May 26 '19 at 11:37 Community♦ 1

4

votes

1

answer

72

views

Why not a $coNP$ hierarchy?

complexity-theory complexity-classes

Dec 14 '17 at 12:14 fade2black 9,392

2

4

votes

1

answer

504

views

Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

complexity-theory complexity-classes

May 22 '16 at 20:54 Community♦ 1

4

votes

1

answer

1k

views

A simple question on #P

complexity-theory

Sep 28 '13 at 0:29 David Richerby 78.6k

2

3

votes

1

answer

157

views

CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP?

complexity-theory np complexity-classes

Jan 2 '20 at 10:52 xskxzr 6,539

3

votes

0

answers

42

views

Does $P=PP$ or $P=PSPACE$ have consequences for algebraic class problem $VP=VNP$?

complexity-theory counting

Jul 18 '19 at 9:00 1.. 2,692

1

3

votes

1

answer

54

views

Pebble game lower bound?

complexity-theory turing-machines time-complexity np lower-bounds

May 31 '19 at 14:29 Yuval Filmus 247k

3

votes

0

answers

24

views

$NP$, $P^{TFNP}$ and $P^{UP}$

complexity-theory np

May 27 '19 at 8:05 dkaeae 4,789

3

votes

1

answer

64

views

Why does not valiant's reduction show NP=RP?

complexity-theory counting

May 26 '19 at 21:41 Yuval Filmus 247k

1

3

votes

1

answer

133

views

On the exponential hierarchy?

complexity-theory complexity-classes

Jan 2 '19 at 13:02 Community♦ 1

3

votes

1

answer

103

views

Is it NP-complete to decide if chromatic and clique numbers agree?

complexity-theory graphs np-complete reductions

Oct 24 '16 at 13:35 Yuval Filmus 247k

1

3

votes

1

answer

72

views

Is it NP complete to decide whether a graph has bigger clique or bigger independence number?

np-complete

May 3 '15 at 11:54 Tom van der Zanden 12.7k

1

3

votes

1

answer

76

views

On approximations and reductions

complexity-theory reductions

Oct 2 '13 at 6:55 Community♦ 1

2

votes

1

answer

56

views

NP-completeness of a problem with pretty fast algorithm

algorithms complexity-theory time-complexity np-complete np

Jan 26 '20 at 11:07 Juho 20.7k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

148 Questions

Simple interepretation problem regarding Polynomial Hierarchy?

Software for testing graph homomorphism

$\mathsf{PP=RP}$ consequences

Relativization results in class separation

Randomized and deterministic reduction

On complete problems for $P/poly$ and $BPP$

If NP is a subset of DTIME[n^O(log n)] then what happens?

Adleman's theorem to $\mathsf{P=BPP}$

Why does this not prove $P\neq NP$?

Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?

Sensitivity and Block sensitivity

Is complexity of $GI_{di}$ same as $GI_{un}$?

A containment result in complexity

How does Grover's Quantum Sorting avoid reading the list?

Modulo operation in monotone complexity

What is the consequence of $\oplus P\neq PP$?

Does real linear programming produce bipartite perfect matching using maxflow reduction?

Why not a $coNP$ hierarchy?

Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

A simple question on #P

CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP?

Does $P=PP$ or $P=PSPACE$ have consequences for algebraic class problem $VP=VNP$?

Pebble game lower bound?

$NP$, $P^{TFNP}$ and $P^{UP}$

Why does not valiant's reduction show NP=RP?

On the exponential hierarchy?

Is it NP-complete to decide if chromatic and clique numbers agree?

Is it NP complete to decide whether a graph has bigger clique or bigger independence number?

On approximations and reductions

NP-completeness of a problem with pretty fast algorithm