Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

more tags

Active Hot Week Month

0

votes

0

answers

36

views

Randomized Reduction for Maximization Problem

cc.complexity-theory complexity-classes randomness

asked Jan 19 at 17:14 tc1729 101

-3

votes

0

answers

58

views

Violating the hierarchy theorems mildly

cc.complexity-theory complexity-classes big-picture hierarchy-theorems time-hierarchy

asked Jan 15 at 8:09 T.... 10.8k

-1

votes

0

answers

44

views

Parallel Tractability

ds.algorithms complexity-classes dc.parallel-comp

modified Jan 9 at 4:36 Ar1Bis 1

2

votes

0

answers

83

views

What is the difference between ${\bf P ^{\bf FewP}}$ and ${\bf UP ^{\bf FewP}}$?

complexity-classes

asked Jan 7 at 15:53 Theodore Payton 21

6

votes

1

answer

416

views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

complexity-classes oracles nexp

modified Jan 2 at 19:01 Community♦ 1

12

votes

1

answer

862

views

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

cc.complexity-theory graph-theory complexity-classes sat counting-complexity

modified Dec 25 '19 at 16:41 Tayfun Pay 2,499

5

votes

1

answer

174

views

If NP in BPP then NP equals RP

reference-request complexity-classes approximation

answered Dec 22 '19 at 20:40 Ryan Williams 24.5k

4

votes

0

answers

73

views

BPP fragment of a PSPACE complete problem

complexity-classes randomness

modified Dec 22 '19 at 20:25 Shaull 3,931

1

vote

1

answer

70

views

The decision procedure of theory of closed real field is in NP-hard?

cc.complexity-theory np-hardness complexity-classes computational-geometry

answered Dec 21 '19 at 7:32 David Eppstein 47.6k

4

votes

0

answers

121

views

Terminology: FNP, with P replaced by NP?

cc.complexity-theory complexity-classes

asked Dec 9 '19 at 12:11 Jukka Suomela 10.7k

19

votes

2

answers

618

views

PPAD and Quantum

cc.complexity-theory complexity-classes quantum-computing cr.crypto-security nash-equilibrium

modified Nov 29 '19 at 5:50 Gil Kalai 5,693

0

votes

0

answers

67

views

Does Descriptive Complexity techniques have the naturalisation barrier?

complexity-classes descriptive-complexity natural-proofs

asked Nov 26 '19 at 6:45 Ramit 21

3

votes

1

answer

93

views

Term for a set that is not immune

complexity-classes fl.formal-languages

modified Nov 23 '19 at 19:44 Bjørn Kjos-Hanssen♦ 4,218

7

votes

2

answers

855

views

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

complexity-classes reductions np-complete physics statistical-physics

modified Nov 19 '19 at 13:12 0x90 447

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled