Hottest Questions This Month

8

votes

3

answers

434

views

Is the wording of Google's QC Supremacy valid?

quantum-computing

answered Oct 29 at 23:22 CognizantApe 141

7

votes

2

answers

305

views

How to efficiently read the theoretical computer science research papers?

soft-question

modified Oct 26 at 18:44 Aryeh 7,847

6

votes

1

answer

154

views

Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?

descriptive-complexity

answered Nov 11 at 17:29 Emil Jeřábek supports Monica 10.9k

5

votes

1

answer

189

views

What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?

cc.complexity-theory ds.algorithms circuit-complexity sat big-list

answered Oct 29 at 16:15 Robert Andrews 338

6

votes

2

answers

146

views

Computing the edge orbits of a graph (and discussing definitions)

graph-theory reductions graph-colouring symmetry automorphism

answered Oct 22 at 19:33 Joshua Grochow 31.8k

5

votes

1

answer

171

views

Document references describing weaknesses for cutting planes and algebraic proof system?

cc.complexity-theory cg.comp-geom proofs proof-complexity

modified Nov 4 at 7:50 notautogenerated 166

3

votes

1

answer

167

views

Qubit gates in google supremacy

cc.complexity-theory quantum-computing big-picture dc.parallel-comp sample-complexity

modified Nov 6 at 13:50 Peter Shor 22.4k

3

votes

1

answer

126

views

Co-NP definition

complexity-classes

answered Oct 27 at 22:22 Daniel 186

1

vote

3

answers

260

views

what is a model of computation, mathematically? [on hold]

fl.formal-languages big-picture machine-models

modified Nov 13 at 17:34 Hermann Gruber 4,210

4

votes

1

answer

149

views

On complexity class $\mathsf{\Pi_2 L}$

cc.complexity-theory complexity-classes space-complexity

modified Oct 21 at 14:42 Alexey Milovanov 1,457

5

votes

1

answer

190

views

Site with collection of exercises in TCS?

soft-question big-list education

modified Nov 3 at 9:24 Manish Kumar 41

1

vote

2

answers

174

views

Why NL is not L

turing-machines space-bounded logspace

answered Nov 7 at 13:27 Lieuwe Vinkhuijzen 1,260

4

votes

1

answer

271

views

Which complexity class does this problem belong to?

cc.complexity-theory complexity-classes

modified Nov 9 at 21:56 Neal Young 4,583

7

votes

1

answer

178

views

NP-hardness of a planar SAT variant

np-hardness sat planar-graphs graph-drawing

modified Oct 28 at 20:22 squire 71

1

vote

1

answer

103

views

How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense? [closed]

cc.complexity-theory quantum-computing church-turing-thesis

answered Oct 30 at 21:52 Greg Kuperberg 451

3

votes

1

answer

126

views

Are endmarkers necessary for Deterministic Pushdown Automata?

automata-theory

modified Nov 13 at 21:16 Bjørn Kjos-Hanssen♦ 4,153

3

votes

1

answer

247

views

Complexity classes not closed under intersection and union

cc.complexity-theory

modified Nov 12 at 18:40 Hermann Gruber 4,210

1

vote

1

answer

144

views

What languages can be reduced to a NP-complete problem in polynomial time

np-hardness sat reductions np-complete

answered Oct 28 at 23:05 Or Meir 4,675

1

vote

1

answer

65

views

Are there common names for the subtiers of PTIME?

cc.complexity-theory complexity-classes time-complexity

answered Oct 21 at 18:28 Gamow 4,562

1

vote

2

answers

136

views

Are patents good sources for academic research?

soft-question research-practice

modified Nov 1 at 20:07 Hermann Gruber 4,210

4

votes

1

answer

77

views

Is the isomorphism problem between posets represented by DAGs GI-complete?

cc.complexity-theory graph-isomorphism directed-acyclic-graph partial-order

modified Nov 7 at 6:47 Laakeri 390

2

votes

1

answer

83

views

Diameter vs. Tractability

graph-algorithms np-hardness fixed-parameter-tractable diameter

answered Oct 25 at 23:21 David Eppstein 47.3k

2

votes

1

answer

136

views

Solving an online problem without maximizing or minimizing an objective

online-algorithms

modified Nov 3 at 0:17 Neal Young 4,583

3

votes

1

answer

168

views

Level $k$ bounds in Analysis of Boolean functions

co.combinatorics boolean-functions fourier-analysis

modified Oct 23 at 9:14 kodlu 1,580

1

vote

1

answer

110

views

How to design an online algorithm for secretary problem with multiple players?

online-algorithms

answered Nov 6 at 15:13 Neal Young 4,583

4

votes

0

answers

163

views

Advice for new grad student [closed]

soft-question

asked Oct 30 at 6:38 Drew Brady 193

5

votes

0

answers

123

views

How much does treewidth changes after removal of a path?

graph-theory treewidth

modified Nov 4 at 18:46 Artur Riazanov 290

4

votes

0

answers

141

views

LogSpace reductions vs. PTime reductons for defining PSpace-completeness

reductions pspace

modified Oct 24 at 15:30 MdAyq 1

1

vote

1

answer

85

views

What Is the Complexity of This Two-to-One Matching Problem?

np-hardness reductions

modified yesterday Antti Röyskö 101

8

votes

0

answers

107

views

Is APSP verification easier than APSP?

graph-algorithms shortest-path fine-grained

asked Nov 6 at 20:49 GMB 1,983

-3

votes

1

answer

81

views

Example of decidable NP-hard problem that is not NP-complete [closed]

np-hardness np-complete examples

modified Nov 8 at 3:53 nathan34 36

2

votes

0

answers

132

views

How do computers check if two functions are the same?

lo.logic functional-programming proof-assistants

asked Nov 11 at 13:18 Student 129

7

votes

0

answers

125

views

Optimal bee swarm plots: NP-hard?

np-hardness cg.comp-geom

modified Oct 30 at 2:34 nathan34 36

1

vote

0

answers

96

views

Can Category Theory help us prove P != NP?

ct.category-theory p-vs-np

asked Oct 21 at 16:44 Yamar69 434

0

votes

0

answers

88

views

A Multiple Online Matching Problem?

online-algorithms

modified Nov 11 at 14:28 zdm 345

2

votes

0

answers

83

views

Why wouldn't showing tautologies don't have short general Frege proofs suffice to separate NP from P?

proof-theory

asked Nov 3 at 14:06 Jérôme Verstrynge 211

0

votes

0

answers

82

views

Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?

zero-knowledge

asked Nov 8 at 12:03 Burak 161

0

votes

1

answer

60

views

Singular Value in Machine Learning

machine-learning

answered Nov 8 at 19:40 D.W. 8,461

4

votes

0

answers

77

views

Is the Complexity Zoo Inclusion Diagram exclusively about classes of decision problems?

circuit-complexity circuit-depth

modified Nov 5 at 7:06 Bjørn Kjos-Hanssen♦ 4,153

5

votes

0

answers

56

views

What are some examples of algorithmic applications of noncommutative rational identity testing?

cc.complexity-theory ds.algorithms graph-algorithms polynomials algebraic-complexity

asked Nov 7 at 18:16 Naysh 233

1

vote

1

answer

55

views

Characterize a point cloud

machine-learning

modified Oct 23 at 9:09 moi 127

2

votes

0

answers

63

views

is factoring harder than deciding if all prime factors lie in a particular residue class?

nt.number-theory

modified Nov 8 at 8:50 Tim kinsella 241

-1

votes

1

answer

47

views

How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it [closed]

boolean-functions circuits minimization

modified Nov 11 at 10:46 dnn 1

4

votes

0

answers

60

views

Short $\exists$SO sentences over strings that define an NP-complete problem

reference-request np-complete finite-model-theory

modified Oct 26 at 8:01 Marzio De Biasi 20.8k

2

votes

0

answers

60

views

Quantum advantage beyond the black-box model

soft-question quantum-computing

asked Oct 24 at 10:35 Lwins 365

0

votes

0

answers

59

views

Turing meta-oracle

computability oracles decidability halting-problem recursive

modified Oct 23 at 2:15 Solomon Ucko 109

-1

votes

0

answers

57

views

Dependent type theory where branching information informs typing derivations?

reference-request pl.programming-languages dependent-type

modified Nov 11 at 16:42 user833970 514

Top Questions

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.