Hottest Questions Today

0

votes

1

answer

29

views

Why are all finite languages regular? [on hold]

regular-language

answered 5 hours ago Zed 26

0

votes

0

answers

14

views

Is P-complete self-reducible?

asked 8 hours ago Frank Vega 22

2

votes

0

answers

55

views

What are CS blogs for puzzles/games?

soft-question

modified 18 hours ago aaaa 28

-1

votes

0

answers

23

views

Counting class for DP problems

time-complexity sat counting-complexity

asked 20 hours ago Andrius Vaicenavicius 44

-1

votes

0

answers

42

views

On derandomizing $BPP$ problem

derandomization polynomial-hierarchy

modified 20 hours ago Brout 4,865

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

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

0

votes

0

answers

17

views

Bi-criteria combinatorial approximation algorithms for min k-vertex cover

approximation

modified 5 hours ago Television 104

-2

votes

0

answers

26

views

The maximum-weight subgraph problem, NP-hard? approximation?

np-hardness approximation

modified yesterday Tomlin 2

-1

votes

0

answers

16

views

Is this a correct way to prove the inapproximability of general k-center?

approximation-algorithms approximation-hardness

modified yesterday Pareod 1

-1

votes

0

answers

16

views

Finding all spanning trees of a directed graph

graph-algorithms directed-acyclic-graph spanning-tree

asked yesterday user3639557 99

-1

votes

0

answers

30

views

Nondominated Sorting Tradeoff Curves [on hold]

ds.algorithms sorting

asked 2 days ago LunarLlama 1

-2

votes

0

answers

22

views

Complexity of a Subset Sum variant with target dependent on elements

cc.complexity-theory reference-request np-hardness

modified 2 days ago CRD 1

1

vote

0

answers

19

views

Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

fl.formal-languages context-free compilers

asked 2 days ago Berserker 76

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

1

vote

1

answer

52

views

Name for a special family of languages?

automata-theory

answered 5 hours ago Zed 26

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

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

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

-1

votes

0

answers

23

views

Encoding naturals in the calculus of constructions and in a language like Idris

lo.logic type-theory proof-theory proof-assistants

asked Feb 15 at 15:24 0xd34df00d 99

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

-1

votes

0

answers

50

views

Is there any approximation factor for this algorithm?

approximation-algorithms approximation

modified Feb 14 at 19:57 Payam Esfandiari 1

8

votes

4

answers

279

views

List of quantum-inspired algorithms

quantum-computing randomized-algorithms

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

-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

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

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

1

vote

0

answers

37

views

Sketching order statistics of a stream

data-streams sketching

modified Feb 14 at 19:46 AmeerJ 322

-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

6

votes

1

answer

147

views

Infinite process balls in bins problem

pr.probability

modified 2 days ago Mister R 69

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

-1

votes

0

answers

20

views

What makes MLT-3 better than B8ZS encoding?

encoding network-modeling ni.networking-internet

asked Feb 14 at 15:17 Joeytje50 99

0

votes

0

answers

28

views

Derive quantum state (bloch sphere) [closed]

quantum-computing quantum-information

modified Feb 14 at 9:54 Roma Karageorgievich 101

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

5

votes

1

answer

89

views

Is F<: with bottom undecidable?

pl.programming-languages

modified 11 hours ago Jason Hu 171

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

0

votes

0

answers

22

views

Computing a sum of products of ratios of QAP-like functions

np-hardness

asked Feb 13 at 3:35 passerby51 158

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

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

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

votes

0

answers

16

views

Eigenvalues of almost Laplacian matrix, particular structure

graph-algorithms co.combinatorics approximation-algorithms

asked Feb 12 at 18:54 user6458 1

0

votes

0

answers

43

views

$k$th element in data stream

approximation-algorithms streaming-algorithms

modified Feb 11 at 8:45 Jan Johannsen 3,874

-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

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

-2

votes

0

answers

41

views

How many succinctly generated circuits are there for a given circuit size?

circuit-complexity enumeration

asked Feb 8 at 18:12 user138901 41

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

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

Top Questions

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