Hottest Questions This Month

11

votes

8

answers

2k

views

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

answered 9 hours ago gnasher729 23.6k

6

votes

4

answers

4k

views

How is ‘x + ½ = 2 and x ∈ ℤ’ an open statement?

first-order-logic

modified Oct 15 at 2:10 John L. 27k

3

votes

2

answers

3k

views

Do Turing machines have memory registers?

formal-languages turing-machines

modified Sep 28 at 9:53 ttnick 1,315

2

votes

3

answers

418

views

Why is SAT based on the CNF?

satisfiability boolean-algebra propositional-logic

modified Oct 6 at 15:35 Monty Thibault 46

4

votes

1

answer

619

views

Proofs of reduction of any hard problem

complexity-theory np-complete np-hard polynomial-time polynomial-time-reductions

modified Oct 3 at 18:41 Yuval Filmus 259k

3

votes

3

answers

124

views

Solve $T (n) = T (\frac n2) + n(2 - \cos n)$

recurrence-relation discrete-mathematics

answered Sep 25 at 19:52 Steven 19.5k

0

votes

1

answer

243

views

Best algorithm to find "deepest" interval

algorithms time-complexity intervals

answered 2 days ago DMGregory 281

2

votes

2

answers

389

views

Minimize the expected value of money spent on boxes until the prize is found

algorithms optimization

modified Oct 11 at 14:40 user2357112 supports Monica 310

4

votes

2

answers

779

views

What empirical evidence do we have for or against a correlation between fault density and LOC?

statistics

modified Oct 12 at 15:27 gnasher729 23.6k

3

votes

1

answer

359

views

Stability of QuickSort Algorithm

algorithms sorting quicksort

answered Oct 2 at 18:40 Pål GD 11.3k

1

vote

2

answers

367

views

Why timeout in TCP is not a predefined fixed value?

computer-networks tcp

modified Oct 16 at 22:17 Effie 149

4

votes

1

answer

295

views

Optimal stacking of bricks

algorithms

answered 10 hours ago Yuval Filmus 259k

2

votes

4

answers

117

views

Why was the fast inverse square root algorithm so ingenious?

algorithms algorithm-analysis software-engineering c

answered Oct 9 at 20:04 TEMLIB 1,736

5

votes

1

answer

117

views

Is classical algorithms a dead research field?

algorithms graphs research

modified Oct 3 at 13:17 Rodrigo de Azevedo 858

0

votes

1

answer

134

views

Adding a finite set to a non-regular language

regular-languages

modified Oct 8 at 10:01 Yuval Filmus 259k

3

votes

1

answer

188

views

Finding the most profitable path

algorithms graphs shortest-path

modified Oct 18 at 18:06 Steven 19.5k

1

vote

1

answer

174

views

NP-completeness of satisfiability of formula over 50 variables

complexity-theory np-complete np

modified Oct 11 at 18:51 Yuval Filmus 259k

1

vote

1

answer

121

views

A computable language with a non-computable language that is prefix-free

formal-languages computability

modified 22 hours ago Addem 227

3

votes

2

answers

66

views

Algorithm that finds a matrix with a specific number of 1s in its rows & columns

algorithms greedy-algorithms matrices

modified Oct 22 at 2:14 narek Bojikian 3,898

0

votes

1

answer

137

views

Why REC languages is undecidable under emptiness and finiteness?

turing-machines undecidability halting-problem decidability

modified Oct 14 at 18:08 Steven 19.5k

5

votes

1

answer

155

views

Is there an instance of 3-SAT in less than 100 variables that no one has been able to solve?

np-complete satisfiability 3-sat

modified 22 hours ago Rodrigo de Azevedo 858

1

vote

1

answer

57

views

Why equality is decidable for regular language but not for $CFL?$

regular-languages context-free pushdown-automata

modified Oct 12 at 10:54 Punia 1

0

votes

4

answers

89

views

How can I compare two algorithms using their Big-Oh complexities?

time-complexity runtime-analysis big-o-notation

answered Sep 28 at 6:39 Lin Jin 43

1

vote

2

answers

51

views

Are there any programming languages that don't support concurrency out of the box?

concurrency

answered Oct 12 at 23:03 vonbrand 13.5k

6

votes

1

answer

104

views

+50

Bisimulation and the Knaster–Tarski theorem: What does the least fixed point mean?

lattices fixed-point

modified 10 hours ago Reijo Jaakkola 176

-1

votes

2

answers

80

views

Proof of a logical theorem

logic propositional-logic

answered 2 days ago Yuval Filmus 259k

0

votes

2

answers

114

views

Regularity of CFG and DCFL

regular-languages finite-automata context-free undecidability decidability

answered Oct 14 at 6:39 Yuval Filmus 259k

2

votes

0

answers

177

views

Produce a Dynkin system from a finite set of finite sets

algorithms reference-request

modified Oct 5 at 8:53 Martin Rubey 21

1

vote

1

answer

95

views

How, if possible, can we efficiently compute with lazy data structures in 𝜆-calculus?

lambda-calculus functional-programming combinatory-logic

answered Oct 6 at 3:30 Anders Kaseorg 294

4

votes

2

answers

70

views

Is the language "substrings of a regular language that are over half the length of the superstring" regular?

regular-languages automata finite-automata nondeterminism

answered Oct 2 at 8:59 J.-E. Pin 5,820

1

vote

2

answers

68

views

Is $O(\log x) = O(1)$?

big-o-notation

modified Oct 8 at 19:09 zkutch 2,211

0

votes

0

answers

142

views

Problems/properties of dynamic graphs with strong lower bounds

algorithms graphs lower-bounds

modified Oct 19 at 13:30 Tom Finet 202

2

votes

1

answer

67

views

Not understanding step in Karger Algorithm: How to simplify a long product

randomized-algorithms algebra

modified Oct 4 at 12:38 Steven 19.5k

0

votes

1

answer

86

views

If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?

turing-machines np-complete polynomial-time polynomial-time-reductions

modified Oct 3 at 15:46 Punia 1

1

vote

3

answers

85

views

What could be the most efficient algorithm to compare two unsorted arrays?

time-complexity runtime-analysis sorting

modified Oct 20 at 6:44 xskxzr 6,970

0

votes

3

answers

83

views

Can there be a computer without software (only hardware)?

computer-architecture computation-models

modified Oct 20 at 22:05 chichorozov 3

0

votes

1

answer

100

views

Time-varying edge cost Minimum Spaning Tree

algorithms graphs trees greedy-algorithms minimum-spanning-tree

modified Sep 29 at 9:13 Pål GD 11.3k

-3

votes

1

answer

126

views

Print all nodes which are the endpoint of the diameter of a tree

algorithms data-structures trees depth-first-search breadth-first-search

modified Oct 12 at 4:07 John L. 27k

4

votes

1

answer

97

views

Point in Polygon on the sphere

computational-geometry

modified Oct 1 at 7:37 Philip Mayer 53

0

votes

1

answer

58

views

Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

context-free context-sensitive decidability

modified Oct 17 at 12:55 Yuval Filmus 259k

0

votes

1

answer

57

views

How can I optimize the systems in the paper "Ensembling Ten Math Information Retrieval Systems"

algorithm-analysis

modified 17 hours ago Witiko 163

3

votes

1

answer

70

views

Is there a book with 100 reductions?

reductions reference-request books polynomial-time-reductions

answered Oct 6 at 19:49 Yuval Filmus 259k

1

vote

0

answers

114

views

Approximating the number of triangles using $\ell_0$ sampling

algorithms graphs sampling streaming-algorithm

modified Oct 1 at 16:02 felipa 83

2

votes

2

answers

53

views

If L is regular so is the language of compressed doubles

formal-languages regular-languages finite-automata regular-expressions

answered Oct 22 at 10:33 Hendrik Jan 26.2k

1

vote

2

answers

51

views

Is there any programming language focused on atemporality?

programming-languages

answered Oct 3 at 7:29 Andrej Bauer 27.2k

-1

votes

0

answers

107

views

How Should I Represent The Following Sentences As A First-Order Predicate Logic?

logic artificial-intelligence first-order-logic

asked Oct 18 at 8:15 armaan 1

5

votes

0

answers

82

views

Does the concept of "side-effect" predate functional programming?

terminology programming-languages functional-programming history

modified Sep 29 at 10:10 Discrete lizard♦ 6,865

2

votes

1

answer

63

views

How hard is random SAT?

complexity-theory np-complete satisfiability complexity-classes 3-sat

modified 2 days ago Kyle Jones 7,645

Top Questions

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