Hottest Questions Today

-3

votes

0

answers

25

views

<Ursprache> Meta programming language (MPL)

asked 10 hours ago John Galt 1

-1

votes

1

answer

50

views

the shorstest cycle containing two given points

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

answered 2 days ago David Eppstein 47.6k

1

vote

2

answers

76

views

Max flow with restriction of individual flows

max-flow-min-cut max-flow

modified 4 hours ago Neal Young 4,898

10

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

3

votes

0

answers

78

views

Set:Set or Negative Inductives in a Total Language?

pl.programming-languages type-theory lambda-calculus type-systems dependent-type

modified 2 days ago Blaisorblade 1,847

-1

votes

0

answers

20

views

Ask for explanation about the composition of weighted transducers

automata-theory machine-learning

asked 2 days ago j200932 101

0

votes

1

answer

72

views

Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

cc.complexity-theory graph-theory graph-algorithms

answered Jan 21 at 19:19 Michael Lampis 2,889

4

votes

1

answer

185

views

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 Jan 22 at 15:39 Emil Jeřábek supports Monica 11.2k

-1

votes

0

answers

14

views

How to determine count of one child nodes in a collection of tournament heaps using an invariant

tree complexity

asked 2 days ago Over Drive Gain 1

6

votes

1

answer

363

views

Does the MIP* = RE proof work for limited provers?

interactive-proofs

modified Jan 22 at 2:37 Henry Yuen 3,628

5

votes

1

answer

109

views

Known property? Maximum radius of connected induced subgraph

graph-theory

answered Jan 20 at 13:13 C Komus 729

-3

votes

0

answers

34

views

How do I show hamiltonian-cycle ≤pol hamiltonian-path and hamiltonian-cycle ≤pol tsp [closed]

polynomial-time tsp hamiltonian-paths

modified Jan 21 at 20:30 Rapiz 1

2

votes

1

answer

54

views

Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

graph-algorithms graph-colouring treewidth

answered Jan 21 at 8:13 M. kanté 966

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

6

votes

1

answer

72

views

Determining if a word of specific length exists that is not accepted by a NFA

np-hardness time-complexity nondeterminism nfa

modified Jan 19 at 19:20 D.W. 8,836

0

votes

0

answers

73

views

NP-Hard Knapsack Instances

np-hardness optimization

asked Jan 18 at 23:54 FiB 141

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

-2

votes

0

answers

52

views

Undecidable problem involving two TMs [closed]

turing-machines undecidability

asked Jan 18 at 14:56 macao421 11

-1

votes

0

answers

61

views

What is the formal definition of a data structure?

ds.algorithms ds.data-structures turing-machines formal-modeling definitions

modified Jan 18 at 7:48 Guest 19

-3

votes

0

answers

41

views

Time compleixty of permutation

time-complexity

Jan 20 at 5:54

-3

votes

1

answer

85

views

Is this a good definition of computability? [closed]

computability halting-problem formal-modeling church-turing-thesis

modified Jan 16 at 16:40 Shaull 3,931

-2

votes

1

answer

94

views

Minimum vertex cover and odd cycles

graph-theory graph-algorithms

answered Jan 15 at 11:04 Laakeri 482

2

votes

0

answers

85

views

Equational Theories for Type Systems

reference-request pl.programming-languages type-theory

modified Jan 15 at 17:44 Apoorv Ingle 131

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

1

vote

0

answers

73

views

Fast Computation of First k Eigenvectors of Graph Laplacian

reference-request graph-theory spectral-graph-theory

modified Jan 15 at 10:47 Arpit Merchant 41

-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

-3

votes

0

answers

27

views

Denotational semantics of command sequencing [closed]

semantics denotational-semantics imperative-programming

asked Jan 16 at 16:15 Gergely 95

2

votes

0

answers

175

views

Fast algorithms for evaluating functions with high Kolmogorov complexity

reference-request time-complexity dc.parallel-comp kolmogorov-complexity

modified Jan 16 at 15:20 Aidan Rocke 225

4

votes

0

answers

45

views

Computing 3D viewpoint of a set of non-intersecting segments

computational-geometry

modified Jan 15 at 11:36 Shaull 3,931

-1

votes

0

answers

33

views

Why does the meta learning objective function use the joint probability?

machine-learning

asked Jan 15 at 22:34 Ethan Wang 1

18

votes

3

answers

494

views

Examples of the value of proofs for algorithms

ds.algorithms proofs teaching

modified Jan 3 at 18:48 Hermann Gruber 4,299

2

votes

0

answers

101

views

Witness verifiable quantum advantage

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

modified 2 hours ago domotorp 12.4k

14

votes

2

answers

1k

views

NP-hard problems with very fast exponential-time algorithms

ds.algorithms reference-request exp-time-algorithms

modified Dec 31 '19 at 2:43 Neal Young 4,898

2

votes

1

answer

82

views

How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

graph-algorithms computational-geometry

modified Jan 11 at 21:50 Thomas Kalinowski 1,026

-1

votes

0

answers

18

views

Using standard fractal iteration within limits for compression

computational-geometry

asked Jan 15 at 0:16 Er Bosh 1

1

vote

1

answer

122

views

Kolmogorov Complexity of the composition of two computable functions

reference-request kolmogorov-complexity

modified Jan 9 at 10:18 Aryeh 8,048

3

votes

1

answer

130

views

Convex polygons inclusion relation

ds.algorithms computational-geometry polygon convex-hull

modified Jan 8 at 20:16 David Eppstein 47.6k

5

votes

1

answer

178

views

Latest word on cross validation?

machine-learning lg.learning pac-learning

answered Jan 6 at 8:19 Vitaly 881

-1

votes

0

answers

51

views

Is checking time-bounded Kolmogorov complexity of a string claiming to be the shortest string in a certain amount of time EXPTIME?

kolmogorov-complexity exp-time-algorithms

modified Jan 11 at 22:44 Number File 99

-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

5

votes

1

answer

184

views

Applications of Barendregt–Geuvers–Klop conjecture

type-theory lambda-calculus

answered Jan 3 at 15:10 cody 12k

-1

votes

0

answers

56

views

What is Undefined Behaviour mapped to with Curry-Howard Correspondence?

proof-theory curry-howard

asked Jan 9 at 11:56 anonymous 1

4

votes

1

answer

946

views

Is an algorithm with an approximation factor of 4000 useful?

approximation-algorithms approximation

modified Jan 12 at 7:37 Hermann Gruber 4,299

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

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

Top Questions

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