Theoretical Computer Science Stack Exchange

0

votes

0

answers

15

views

Is P-complete self-reducible?

cc.complexity-theory complexity-classes reductions p-hardness

asked 9 hours ago Frank Vega 22

-2

votes

0

answers

58

views

How low can $NC$ be?

cc.complexity-theory complexity-classes

asked Feb 6 at 10:28 Brout 4,865

6

votes

2

answers

764

views

Isn't it trivial to represent any classical physics problem in a Spin-Glass language which is NP-Complete?

complexity-classes reductions np-complete physics statistical-physics

modified Feb 5 at 7:38 0x90 216

-1

votes

0

answers

48

views

Complexity lower bound for problem in $2^k \cdot 2^{|A|}$ with monotonicity in $k$

complexity-classes lower-bounds reductions parameterized-complexity

modified Feb 2 at 14:44 Ayrat 99

9

votes

1

answer

146

views

Natural candidates for NP-E and E-NP

cc.complexity-theory complexity-classes np-complete

answered Jan 26 at 12:19 Lance Fortnow 7,036

13

votes

1

answer

419

views

Is there a P-complete language X such that succinct-X is in P?

cc.complexity-theory complexity-classes reductions succinct

modified Jan 25 at 22:13 Frank Vega 22

3

votes

0

answers

123

views

Random self reducibility and NP

np-hardness complexity-classes reductions

modified Jan 24 at 4:26 user30448 129

35

votes

3

answers

5k

views

P and NP classes explanation through lambda-calculus

cc.complexity-theory complexity-classes turing-machines lambda-calculus

modified Jan 23 at 9:01 Hermann Gruber 3,875

-1

votes

0

answers

48

views

How could the No Free Lunch Theorem be applied to complexity classes

complexity-classes optimization search-problem

asked Jan 20 at 23:40 Shian Shao 4

10

votes

1

answer

369

views

Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

cc.complexity-theory complexity-classes nondeterminism

modified Jan 17 at 15:56 Alex Williams 1

1

vote

0

answers

196

views

BQNC and Abelian Hidden Subgroup Problem

cc.complexity-theory reference-request complexity-classes quantum-computing dc.parallel-comp

modified Dec 17 '18 at 4:19 Brout 4,865

8

votes

1

answer

189

views

How “hard” is it to maximize a polynomial function subject to linear constraints?

cc.complexity-theory complexity-classes time-complexity linear-programming polynomials

modified Dec 16 '18 at 17:39 Gamow 4,069

1

vote

0

answers

266

views

EXPSPACE proof and its implications

cc.complexity-theory complexity-classes time-complexity proofs space-complexity

asked Dec 12 '18 at 14:05 Iago Carvalho 13

4

votes

1

answer

286

views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

complexity-classes oracles nexp

modified Dec 11 '18 at 8:03 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore Our Questions

Is P-complete self-reducible?

How low can $NC$ be?

Isn't it trivial to represent any classical physics problem in a Spin-Glass language which is NP-Complete?

Complexity lower bound for problem in $2^k \cdot 2^{|A|}$ with monotonicity in $k$

Natural candidates for NP-E and E-NP

Is there a P-complete language X such that succinct-X is in P?

Random self reducibility and NP

P and NP classes explanation through lambda-calculus

How could the No Free Lunch Theorem be applied to complexity classes

Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

BQNC and Abelian Hidden Subgroup Problem

How “hard” is it to maximize a polynomial function subject to linear constraints?

EXPSPACE proof and its implications

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

Hot Network Questions