Hottest Questions This Month

8

votes

4

answers

282

views

List of quantum-inspired algorithms

quantum-computing randomized-algorithms

answered Feb 10 at 19:11 Thomas Klimpel 2,048

9

votes

1

answer

146

views

Natural candidates for NP-E and E-NP

answered Jan 26 at 12:19 Lance Fortnow 7,036

6

votes

3

answers

220

views

A partition problem in which some numbers may be cut

np-hardness reductions partition-problem

modified Feb 6 at 20:02 Chao Xu 2,914

6

votes

2

answers

189

views

Is case analysis on normal forms of lambda terms sufficient to prove parametricity results?

lo.logic type-theory normalization parametricity

answered Feb 12 at 19:21 gadmm 51

5

votes

2

answers

101

views

Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

cc.complexity-theory counting-complexity

answered Jan 31 at 20:30 smengel 126

9

votes

1

answer

202

views

What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

cc.complexity-theory lo.logic halting-problem

answered Feb 15 at 3:13 Yonatan N 1,122

6

votes

1

answer

150

views

Minimal generator for a set of sets

reference-request np-hardness set-cover

answered Feb 1 at 12:26 user6192 71

6

votes

1

answer

80

views

Is CoC inconsistent with cnat_ind axiom?

type-theory calculus-of-constructions

answered Jan 24 at 7:32 Andrej Bauer 21.7k

6

votes

1

answer

178

views

Where do people publish/submit their work on type theory?

soft-question type-theory big-list research-practice

answered Jan 27 at 21:44 Andrej Bauer 21.7k

7

votes

1

answer

146

views

P and Descriptive Complexity

lo.logic polynomial-time descriptive-complexity

modified Feb 12 at 7:28 Hermann Gruber 3,875

2

votes

1

answer

71

views

Oncina-Garcia RPNI algorithm for learning DFAs

machine-learning lg.learning regular-language dfa

modified Feb 13 at 12:19 Aryeh 5,574

6

votes

1

answer

147

views

Infinite process balls in bins problem

pr.probability

modified 2 days ago Mister R 69

3

votes

1

answer

75

views

Is there a simple algorithm for proof search on CoC?

type-theory calculus-of-constructions proof-search

modified Feb 15 at 22:11 user833970 311

-2

votes

1

answer

95

views

Does P^NP=NP imply NP=coNP? [closed]

cc.complexity-theory p-vs-np polynomial-hierarchy

answered Feb 8 at 4:34 Andras Farago 5,609

3

votes

1

answer

93

views

Universe polymorphism: the inference of universes and their constraints

type-theory coq type-inference calculus-of-constructions polymorphism

answered Feb 4 at 10:13 Andrej Bauer 21.7k

2

votes

1

answer

116

views

Would an NP-complete public key cryptosystem imply NP=co-NP?

cc.complexity-theory cr.crypto-security

answered Feb 2 at 5:10 M.S. Dousti 12.7k

5

votes

1

answer

89

views

Is F<: with bottom undecidable?

pl.programming-languages

modified 12 hours ago Jason Hu 171

6

votes

0

answers

137

views

Bottleneck $k$-link path in a complete DAG

ds.algorithms

modified Jan 29 at 20:33 Chao Xu 2,914

-1

votes

1

answer

106

views

Why does the Placid Platypus function grow faster than any computable function?

computability turing-machines

answered Feb 13 at 9:14 Aryeh 5,574

2

votes

1

answer

135

views

An equation relating Time complexity, Space complexity, and entropy of output

cc.complexity-theory shannon-entropy

answered Feb 10 at 20:15 usul 5,224

3

votes

1

answer

100

views

Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

fixed-parameter-tractable

answered Feb 16 at 20:42 yassin 136

0

votes

2

answers

69

views

Bellman-Ford with Non-edge-decomposable Path Weights

optimization shortest-path

answered Jan 26 at 4:54 Neal Young 4,284

6

votes

0

answers

112

views

Can reciprocal inputs speed up monotone computations?

cc.complexity-theory circuit-complexity algebraic-complexity arithmetic-circuits

modified Feb 10 at 20:20 Stasys 4,578

0

votes

1

answer

84

views

Definitional equality of recursive function definition by “infinite unfolding”

type-theory dependent-type recursion

modified Feb 14 at 15:25 xavierm02 406

4

votes

0

answers

120

views

Hereditary Substitution with Inductives and Eliminators?

reference-request pl.programming-languages type-theory lambda-calculus dependent-type

modified Feb 5 at 21:24 jmite 793

-3

votes

1

answer

72

views

Are there any known languages in the intersection of NP and co-NP but not in P? [closed]

complexity-classes np

answered Feb 13 at 13:17 Mohammad Al-Turkistany 13.7k

-1

votes

0

answers

103

views

“Computational” Entropy, probability, and if I don't know A and B, I don't know A+B

cr.crypto-security it.information-theory entropy

modified Feb 2 at 10:03 tobiasBora 102

2

votes

1

answer

74

views

Validity of a modal argument about “vagueness”

modified Feb 4 at 17:57 Speakpigeon 13

2

votes

0

answers

91

views

Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

cc.complexity-theory counting-complexity

asked Jan 27 at 17:31 Lorenzo 291

1

vote

0

answers

90

views

Parallel building time of a k-d tree on n points with n processors

time-complexity tree dc.parallel-comp

asked Feb 10 at 16:14 Skrodde 6

1

vote

1

answer

69

views

Computational hardness for sampling a uniform matching

cc.complexity-theory counting-complexity permanent

answered Feb 12 at 8:43 smapers 11

2

votes

1

answer

58

views

Weighted Min-Cut in bounded-genus graphs

cc.complexity-theory planar-graphs max-cut

answered Feb 5 at 16:57 Arnaud 710

2

votes

0

answers

74

views

What's the example of natural transformation in 'Type" that is not a parametric function?

type-theory ct.category-theory natural-transformation

modified Jan 29 at 7:46 Andrej Bauer 21.7k

3

votes

0

answers

67

views

Is it possible to check equality of equi-recursive types, or recursive λ-terms?

type-theory lambda-calculus functional-programming

modified Feb 7 at 18:17 MaiaVictor 1,420

0

votes

1

answer

52

views

About learning a single Gaussian in total-variation distance

ds.algorithms machine-learning lg.learning st.statistics

modified yesterday Clement C. 2,111

2

votes

0

answers

65

views

Best algorithms for real linear programming

cc.complexity-theory reference-request linear-programming fixed-parameter-tractable

asked Feb 7 at 11:34 Brout 4,865

0

votes

0

answers

65

views

Where is the flaw in this proof that an LP solves TSP? [closed]

cc.complexity-theory reference-request linear-programming tsp

asked Feb 14 at 3:46 isaacg 333

0

votes

1

answer

63

views

Lower bound of real valued bounded function

machine-learning lg.learning pac-learning

modified 16 hours ago Aryeh 5,574

3

votes

0

answers

62

views

Is monotone 1-in-3 MAXSAT known to be APX hard?

np-hardness sat approximation-hardness

modified Feb 16 at 1:49 karmanaut 465

2

votes

0

answers

60

views

Complexity of counting Wang tiles

cc.complexity-theory co.combinatorics

asked Feb 6 at 14:02 BGJ 11

-2

votes

0

answers

58

views

How low can $NC$ be?

cc.complexity-theory complexity-classes

asked Feb 6 at 10:28 Brout 4,865

2

votes

1

answer

58

views

Select circle with given radius that contains most points

computational-geometry

answered Jan 28 at 3:18 D.W. 7,336

3

votes

0

answers

57

views

Proof that CIC or Dybjer-style eliminators are strongly-normalizing?

pl.programming-languages type-theory lambda-calculus dependent-type calculus-of-constructions

asked Feb 11 at 22:04 jmite 793

4

votes

1

answer

56

views

Solving an LP with at most m-1 nonzeros

np-hardness linear-programming

answered Jan 27 at 6:29 Erel Segal-Halevi 878

3

votes

0

answers

55

views

What are CS blogs for puzzles/games?

soft-question

modified 19 hours ago aaaa 33

1

vote

0

answers

53

views

What is the computational complexity of determining the mixing time of a Cayley graph?

interactive-proofs markov-chains

asked Jan 22 at 14:22 Mark S 372

Top Questions

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