Hottest Questions This Month

26

votes

4

answers

6k

views

Which Grows Faster: Factorial or Double Exponentiation

time-complexity

modified Nov 27 at 12:06 OmG 2,661

12

votes

4

answers

15k

views

Water Jug Problem in AI

artificial-intelligence

modified Nov 14 at 22:03 Dewi Morgan 200

12

votes

3

answers

210

views

Is O((n^2)*log(n)) greater than O(n^(2.5))?

asymptotics landau-notation

modified Nov 26 at 19:44 Raphael♦ 66.5k

13

votes

5

answers

1k

views

NP-hard problems but only for n≥3

np-complete

answered Nov 18 at 12:17 gnasher729 16k

5

votes

3

answers

878

views

How to determine minimum word length of regular language

regular-languages regular-expressions

modified Nov 18 at 7:28 Webastronaut 53

6

votes

3

answers

960

views

Space complexity for storing integers in Python

space-complexity integers python

modified Nov 11 at 18:26 MurksVomOrk 11

7

votes

5

answers

155

views

Is $n^{1/\log \log n} = O(1)$?

asymptotics

answered Nov 27 at 10:50 Ashwin Ganesan 329

8

votes

4

answers

189

views

Stack Permutation Algorithm

algorithms permutations stacks

modified yesterday Guillermo Phillips 267

5

votes

2

answers

544

views

Are there any proofs of exponential lower bound time complexity

complexity-theory time-complexity decision-problem

modified Nov 20 at 10:08 greybeard 534

1

vote

1

answer

510

views

How to prove graph isomorphism is NP?

complexity-theory np graph-isomorphism

answered Dec 2 at 23:40 Yuval Filmus 213k

5

votes

2

answers

210

views

Are “logarithm types” a thing?

type-theory

answered Dec 1 at 16:52 Dan Doel 1,136

3

votes

3

answers

121

views

Are regular languages and their regular expressions part of computer science?

terminology logic regular-expressions mathematical-programming

modified Nov 13 at 16:22 reinierpost 3,530

4

votes

1

answer

500

views

Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

complexity-theory time-complexity

answered 2 days ago Arno 689

-3

votes

2

answers

169

views

Is automata concept theorized in computer science and what would be a simple example?

automata terminology

modified Nov 30 at 10:00 David Richerby 76.1k

9

votes

3

answers

264

views

+150

Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence

algorithms integers subsequences

modified 2 days ago HEKTO 2,075

3

votes

3

answers

248

views

Regular Expression with at least one a, even number of b

regular-expressions

answered Nov 14 at 16:12 holf 676

3

votes

3

answers

142

views

Is it possible that the subtraction between two undecidable languages is regular?

turing-machines regular-languages undecidability semi-decidability

answered Nov 21 at 8:00 J.-E. Pin 5,168

3

votes

3

answers

131

views

How to find a path that connects all the dots in the matrix?

algorithms graphs search-algorithms matrices hamiltonian-path

answered Nov 22 at 18:18 Carlos Linares López 3,041

3

votes

2

answers

111

views

Time Complexity: Why does $n^n$ grow faster than $n!$?

time-complexity

modified Nov 25 at 22:32 Yuval Filmus 213k

2

votes

1

answer

138

views

Example of non-regular context free language L such that prefix(L) is regular

regular-languages context-free

answered Nov 13 at 22:30 Daniel 342

6

votes

1

answer

65

views

Is 3-colouring NP-hard for 5-colourable graphs?

complexity-theory np-hard

modified Nov 15 at 6:39 András Salamon 2,942

5

votes

2

answers

228

views

Recover an array from its insertion indices

algorithms arrays

modified Nov 20 at 15:46 user111398 256

3

votes

2

answers

137

views

Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a

regular-languages formal-grammars

answered Nov 30 at 22:11 templatetypedef 7,634

3

votes

1

answer

162

views

how to check whether a flow network contains unique maximum flow?

algorithms network-flow

modified Nov 21 at 13:41 tjhighley 497

5

votes

1

answer

95

views

Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

complexity-theory np-complete reductions

answered Nov 21 at 15:03 Antti Röyskö 191

4

votes

1

answer

312

views

How to determine if a language is deterministic context-free language?

context-free nondeterminism

modified Nov 18 at 3:21 Vimal Patel 442

-2

votes

2

answers

77

views

Why Rice theorem work for decidability?

formal-languages turing-machines formal-grammars undecidability rice-theorem

modified Nov 17 at 8:25 anir 1,135

5

votes

1

answer

119

views

Using decision oracle to solve optimization problem of maximum polyomino tiling

algorithms np-complete np

answered yesterday j_random_hacker 3,325

1

vote

2

answers

152

views

Removing vertices from a labelled graph

graphs

modified 14 hours ago Tom van der Zanden 10.7k

5

votes

2

answers

71

views

Modifying digraph to make it strongly connected

algorithms graphs

answered Nov 21 at 23:39 j_random_hacker 3,325

2

votes

1

answer

89

views

Example of two undecidable languages that cannot be reduced to each other

formal-languages turing-machines automata reductions

modified Nov 22 at 1:41 Joe 111

4

votes

2

answers

132

views

+150

How to devise an algorithm to generate a random but valid train track layout?

computational-geometry randomized-algorithms

modified 4 hours ago reinierpost 3,530

3

votes

1

answer

129

views

Does there exist a subset of substrings for reconstructing another string?

algorithms strings substrings

modified Dec 1 at 1:54 Travis Wells 209

4

votes

1

answer

76

views

Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$

asymptotics big-o-notation

modified Nov 18 at 13:32 Yuval Filmus 213k

3

votes

2

answers

46

views

Is it standard for VMs to run *= computationallyHeavyFunction() if the left hand side is 0?

computer-algebra

answered Nov 26 at 12:47 AProgrammer 2,824

1

vote

1

answer

97

views

What does it mean by “not recursively enumerable”?

formal-languages

modified Nov 11 at 16:46 f9c69e9781fa194211448473495534 340

0

votes

1

answer

75

views

What is the worst case for C++ “sort” function?

quicksort

modified Nov 14 at 15:58 Steven 2,814

0

votes

1

answer

96

views

Is this statement of P = NP in Agda correct?

complexity-theory type-theory p-vs-np dependent-types agda

modified Nov 18 at 17:58 helianthus 51

3

votes

3

answers

117

views

Does White never lose in Chess if Chess is solved?

space-complexity search-problem board-games search

modified Nov 27 at 7:56 108880 153

4

votes

1

answer

90

views

How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

formal-languages regular-languages pumping-lemma

modified yesterday Apass.Jack 19.6k

3

votes

2

answers

54

views

Fermat's last theorem: How to (partially) solve by programs

discrete-mathematics mathematical-programming

modified Nov 30 at 12:18 xxx--- 277

2

votes

3

answers

67

views

How to prove that this language is not regular?

formal-languages regular-languages

modified Nov 27 at 10:37 reinierpost 3,530

3

votes

1

answer

52

views

Can current quantum computers decide languages that Turing Machines cannot?

turing-machines reductions undecidability quantum-computing church-turing-thesis

answered Nov 13 at 7:22 Laakeri 445

3

votes

1

answer

65

views

Kolmogorov Complexity of String Concatenation

kolmogorov-complexity

modified Nov 24 at 20:47 Glorfindel 266

0

votes

1

answer

82

views

What programming languages always learned in computer science B.Sc.?

formal-languages education

modified Nov 12 at 22:44 JohnDoea 35

5

votes

1

answer

49

views

What is meant by a full abstract model of a lambda-calculus like language?

lambda-calculus semantics

modified Nov 11 at 17:15 Apoorv Ingle 131

1

vote

1

answer

103

views

How do I reduce subset sum to another problem in NP?

algorithms complexity-theory reductions np-hard

modified 22 hours ago Juho 18.1k

1

vote

2

answers

36

views

Summation of asymptotic notation

asymptotics big-o-notation

modified Nov 20 at 17:00 Yuval Filmus 213k

Top Questions

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