Hottest Questions Today

4

votes

1

answer

382

views

Relationship between two graph optimization problems

answered 10 hours ago Antti Röyskö 186

0

votes

2

answers

98

views

Is the decidability of a language decidable? [on hold]

fl.formal-languages computability turing-machines decidability

modified 5 hours ago Dylan McKay 548

0

votes

0

answers

73

views

Why P/poly can solve Unary halting problem while turing machine can't [on hold]

turing-machines advice-and-nonuniformity halting-problem undecidability

asked 2 days ago Zachary HUANG 29

1

vote

3

answers

289

views

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

fl.formal-languages big-picture machine-models

modified 19 hours ago Ringminustwo 127

-1

votes

0

answers

28

views

Scheduling and routing

ds.algorithms reference-request graph-theory graph-algorithms optimization

asked 2 days ago Jebus 11

2

votes

0

answers

50

views

How hard is it to approximate distance of linear code

np-hardness approximation-hardness coding-theory

asked Nov 15 at 12:23 Bartolinio 203

1

vote

1

answer

99

views

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

np-hardness reductions

modified Nov 15 at 13:36 Antti Röyskö 186

-2

votes

0

answers

35

views

Can Christofides algorithm provide different solution in different execution?

graph-algorithms approximation-algorithms tsp

asked Nov 15 at 14:05 LSG 97

-3

votes

0

answers

59

views

Complexity theory in non-TM models and randomness and complete problems? [on hold]

cc.complexity-theory turing-machines big-picture big-list randomness

modified Nov 15 at 14:26 VS. 377

3

votes

1

answer

149

views

Are endmarkers necessary for Deterministic Pushdown Automata?

automata-theory context-free

modified yesterday Hermann Gruber 4,220

-3

votes

0

answers

24

views

Runtime of flood fill with multiple centres

ds.algorithms

asked Nov 14 at 17:07 user55290 1

6

votes

1

answer

162

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

-1

votes

0

answers

23

views

Approximation quality of a simple linearization of binary quadratic program

integer-programming approximation

modified Nov 14 at 8:51 randomprime 1

-1

votes

1

answer

46

views

Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$

convex-optimization high-dimensional-geometry function

answered Nov 14 at 4:25 Antti Röyskö 186

2

votes

0

answers

143

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

3

votes

0

answers

55

views

Topologies for modelling divergence in the lambda-calculus

lambda-calculus topology

asked Nov 12 at 12:16 Javier 465

-1

votes

0

answers

58

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

2

votes

0

answers

40

views

Church numerals and Kleene numerals

lambda-calculus

asked Nov 11 at 11:48 Amit. S 113

0

votes

0

answers

48

views

What is the run-time of LP?

approximation-algorithms time-complexity linear-programming

modified Nov 11 at 1:16 gradstudent 1,323

0

votes

0

answers

88

views

A Multiple Online Matching Problem?

online-algorithms

modified Nov 11 at 14:28 zdm 345

0

votes

0

answers

26

views

Understanding non-equivalence of proof lengths according to proof systems

sat np proof-theory

asked Nov 11 at 10:22 Jérôme Verstrynge 211

-1

votes

1

answer

48

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

1

vote

2

answers

180

views

Why NL is not L

turing-machines space-bounded logspace

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

3

votes

1

answer

170

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

-2

votes

1

answer

57

views

Question about the Bits of information

it.information-theory

answered Nov 10 at 1:07 Mark 276

-1

votes

0

answers

25

views

Programming a 2-Tag System

universal-turing-machines

asked Nov 10 at 19:42 Jay McArthur 1

-3

votes

1

answer

84

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

0

votes

1

answer

64

views

Singular Value in Machine Learning

machine-learning

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

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

4

votes

1

answer

274

views

Which complexity class does this problem belong to?

cc.complexity-theory complexity-classes

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

0

votes

0

answers

89

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

2

votes

0

answers

51

views

Lower bounds for list/set data structures without delete

ds.data-structures lower-bounds communication-complexity

modified 5 hours ago Dustin Wehr 193

3

votes

1

answer

251

views

Complexity classes not closed under intersection and union

cc.complexity-theory

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

2

votes

0

answers

65

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

8

votes

0

answers

108

views

Is APSP verification easier than APSP?

graph-algorithms shortest-path fine-grained

asked Nov 6 at 20:49 GMB 1,983

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

-2

votes

0

answers

13

views

What does “proven constructions” mean in the context of Finite Automata? [closed]

automata-theory dfa

modified Nov 11 at 1:56 Novicegrammer 1

5

votes

0

answers

57

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

8

votes

3

answers

437

views

Is the wording of Google's QC Supremacy valid?

quantum-computing

answered Oct 29 at 23:22 CognizantApe 141

-1

votes

0

answers

31

views

Understanding Computability of a Function

cc.complexity-theory computability computable-analysis

asked Nov 8 at 10:25 aomerk 107

2

votes

0

answers

30

views

Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related? [closed]

polynomial-hierarchy semidefinite-programming sum-of-squares

asked Nov 7 at 17:53 guigux 121

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

-1

votes

0

answers

17

views

Is there any better optimization program way instead of state machines?

optimization

asked Nov 8 at 15:19 Владимир Смирнов 99

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

Top Questions

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