Hottest Questions This Month

15 votes

4 answers

2k views

Is there a known polynomial time complexity problem with bad constants?

gnasher729

28.3k

answered Nov 14 at 7:42

6 votes

2 answers

2k views

What does it mean to prove the halting problem is undecidable "using arithmetization"?

Sam Gutkind

31

answered Nov 14 at 0:56

6 votes

1 answer

706 views

Representing binary functions with a finite gate set without exponential blow-up?

D.W.♦

156k

answered Nov 2 at 18:29

4 votes

3 answers

621 views

What is practically preventing us from applying set-theoretic types in engineering?

Sorawee Porncharoenwase

103

modified 10 hours ago

4 votes

1 answer

703 views

Is Determining the Number of distinct Prime Factors Polynomial?

Mark Dominus

1,527

modified 10 hours ago

1 vote

2 answers

364 views

Does there exist an context free language L such that L∩L^R is not context free?

Hendrik Jan

29.8k

modified Nov 20 at 12:07

0 votes

1 answer

235 views

What is the simplified form of this big o

SilvioM

588

answered Nov 26 at 14:30

-2 votes

2 answers

167 views

Could this novel algorithm be qualified to be published in Nature or Science

Shawxing Kwok

5

modified 12 hours ago

2 votes

1 answer

90 views

Optimal torch placement in voxel games

Steven

28.2k

modified Nov 9 at 10:27

2 votes

2 answers

108 views

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

Hugh Mann

67

answered Nov 16 at 22:02

-3 votes

1 answer

102 views

If Q* can break encryption would that prove P=NP?

gnasher729

28.3k

answered Nov 25 at 22:58

3 votes

0 answers

126 views

Recover unknown vector through shifted argmax queries

Florian Tramèr

31

asked Nov 15 at 14:59

1 vote

2 answers

57 views

Solve the recurrence $T(n)=T(n-2)+\frac{1}{\lg{n}}$

Nathaniel

12.5k

modified Nov 15 at 13:56

1 vote

2 answers

71 views

Union of non regular and regular language

Hendrik Jan

29.8k

answered Nov 7 at 14:03

0 votes

1 answer

85 views

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Kai

663

modified Nov 21 at 14:05

3 votes

1 answer

83 views

How many random bits does this algorithm use on average?

D.W.♦

156k

modified Nov 15 at 22:58

1 vote

1 answer

83 views

Algorithm for optimal item selections

Inuyasha Yagami

5,797

modified Nov 2 at 23:27

1 vote

1 answer

76 views

Number of decycling sets in a 3-regular planar graph

Inuyasha Yagami

5,797

answered Nov 1 at 19:30

0 votes

2 answers

96 views

( Soft question ) P vs NP - is such a situation possible?

gnasher729

28.3k

modified Nov 9 at 11:48

0 votes

1 answer

58 views

Can you compute a majority function of n-bits using an O(n) size circuit?

Steven

28.2k

answered Nov 24 at 21:18

0 votes

1 answer

57 views

Is L={0^n 1^n ∣n≥0} context free language?

Steven

28.2k

modified Nov 13 at 10:26

1 vote

1 answer

91 views

Maximizing sum and product of an array

Inuyasha Yagami

5,797

answered Nov 5 at 2:28

0 votes

1 answer

55 views

Visiting all nodes of a directed graph exactly once (not dfs)

JimN

769

modified yesterday

0 votes

0 answers

90 views

Finding all stable matchings in stable marriage problem

void

1

asked Nov 2 at 10:43

3 votes

1 answer

54 views

What is the complexity of minimising a convex quadratic function over the integers?

D.W.♦

156k

answered Nov 13 at 20:05

1 vote

1 answer

89 views

Is there an efficient algorithm for this ecommerce optimization problem?

Jo Ma

15

modified Nov 7 at 7:59

1 vote

2 answers

87 views

NP-hardness of modified distance-colouring of graphs

Juho

22.5k

answered Nov 25 at 19:31

-1 votes

1 answer

86 views

Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}

Hendrik Jan

29.8k

answered Nov 25 at 19:43

1 vote

0 answers

85 views

Can we compute most significant digit of a binary number in O(1) on RAM model?

Kaveh

22.2k

modified yesterday

0 votes

3 answers

109 views

Testing whether a number (N) is prime or not can be made very fast but it will require storage space

user164680

1

modified yesterday

1 vote

1 answer

63 views

Sorting rational numbers in linear time

gnasher729

28.3k

answered Nov 13 at 0:21

0 votes

1 answer

47 views

How to modify Dijkstra's algorithm to model the path of an electric car?

Hendrik Jan

29.8k

modified Nov 19 at 15:14

2 votes

2 answers

36 views

Is loading from L2 or L3 of multi level cache direct or require a transfer to L1

Netochka Nezvanova

36

answered Nov 23 at 1:19

1 vote

1 answer

59 views

If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine

Yuval Filmus

275k

answered Nov 23 at 19:44

0 votes

1 answer

58 views

$k$-way number contiguous partitioning

VandhuV3Kumar

1

modified Nov 10 at 16:42

1 vote

2 answers

57 views

Complexity of satisfiability for relational logic on the booleans

user1868607

2,184

answered yesterday

0 votes

1 answer

57 views

Turing machine comparing two binary numbers in linear time

Andrej Bauer

30k

modified Nov 12 at 9:27

1 vote

1 answer

44 views

Expected maximum matching size in a random bipartite graphs

D.W.♦

156k

answered Nov 8 at 20:14

0 votes

1 answer

72 views

Formally Verify if a Sequence of Regex-Based Modifications is Idempotent

D.W.♦

156k

modified Nov 15 at 20:01

1 vote

1 answer

56 views

Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth

Steven

28.2k

modified Nov 12 at 11:24

1 vote

2 answers

43 views

In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?

benrg

2,091

answered Nov 21 at 21:22

2 votes

1 answer

55 views

Dinitz’ algorithm in simple unit-capacity networks

Pål GD

15.5k

modified Nov 8 at 10:01

0 votes

2 answers

69 views

How to find prefixes and suffixes for infinite languages? (Automata)

Kai

663

answered Nov 12 at 10:36

0 votes

0 answers

69 views

Is the following a correct proof for the interval covering problem?

VandhuV3Kumar

1

modified Nov 8 at 3:03

1 vote

1 answer

52 views

If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

Alex Meiburg

923

answered Nov 9 at 18:32

3 votes

1 answer

31 views

Increasing families of expander graphs

Yuval Filmus

275k

answered Nov 5 at 18:56

2 votes

2 answers

51 views

Derivation trees to show a given grammar is ambiguous

math boy

1

answered Nov 19 at 2:15

2 votes

1 answer

51 views

Comparison of different algorithms for summing floating point numbers

gnasher729

28.3k

answered Nov 8 at 14:56

Top Questions

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