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 1 Bountied Hot Week Month

19

votes

3

answers

3k

views

Minimum Unsatisfiable 3-CNF Formulae

cc.complexity-theory sat

modified 29 mins ago ian.p.swift 1

-2

votes

1

answer

28

views

the shorstest cycle containing two given points

cc.complexity-theory approximation-algorithms approximation-hardness planar-graphs

answered 6 hours ago David Eppstein 47.5k

4

votes

1

answer

165

views

+100

Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

cc.complexity-theory quantum-computing tradeoff speed-up

modified yesterday Emil Jeřábek supports Monica 11.2k

0

votes

1

answer

68

views

Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

cc.complexity-theory graph-theory graph-algorithms

answered 2 days ago Michael Lampis 2,889

9

votes

2

answers

2k

views

“Almost all objects have property P” vs. “It is easy to test whether an object has property P”

cc.complexity-theory pr.probability

answered Jan 21 at 1:01 Acccumulation 223

0

votes

1

answer

70

views

Is the counting version of 1-in-3 Sat #P-complete?

cc.complexity-theory np-hardness counting-complexity

modified Jan 20 at 18:04 Gamow 4,647

0

votes

0

answers

34

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

24

votes

5

answers

3k

views

Implications of unprovability of $P\neq NP$

cc.complexity-theory np-hardness big-picture proofs p-vs-np

modified Jan 14 at 11:01 Yu Li 1

0

votes

1

answer

163

views

Does two-sided error have more capability than one-sided error?

cc.complexity-theory randomness exp-time-algorithms

answered Jan 11 at 3:38 J.G 436

-3

votes

0

answers

66

views

How can I prove that a specific structure $\Pi_2$ problem is $\Pi_2$-complete?

cc.complexity-theory polynomial-hierarchy

modified Jan 10 at 10:06 MATH_LI 1

2

votes

0

answers

83

views

How fast can we perform DFT on a Log-RAM computer?

cc.complexity-theory machine-models

modified Jan 7 at 3:58 Matt Groff 2,041

3

votes

0

answers

82

views

Isomorphic subforest problem

cc.complexity-theory ds.algorithms reference-request graph-theory

modified Jan 3 at 2:39 Zachary Hunter 315

2

votes

0

answers

94

views

Witness verifiable quantum advantage

cc.complexity-theory quantum-computing ce.computational-finance

asked Dec 29 '19 at 8:33 domotorp 12.4k

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled