Hottest Questions This Month

63

votes

7

answers

14k

views

Is legislation NP-complete?

answered Dec 1 at 18:33 Tom Whitaker Jr 1

21

votes

5

answers

3k

views

Do any two spanning trees of a simple graph always have some common edges?

graphs graph-theory spanning-trees

modified Dec 7 at 14:40 David Richerby 65.3k

10

votes

7

answers

3k

views

O(·) is not a function, so how can a function be equal to it?

complexity-theory asymptotics notation

answered 8 mins ago ezrakilty 1

10

votes

3

answers

2k

views

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

formal-languages regular-languages regular-expressions

modified Nov 19 at 10:03 Laurel 103

14

votes

3

answers

2k

views

Shannon Entropy of 0.922, 3 Distinct Values

information-theory mathematical-foundations entropy binary

modified Nov 19 at 22:33 David Richerby 65.3k

5

votes

3

answers

921

views

Relation between Undecidable problems and NP-Hard

complexity-theory computability undecidability np-hard

modified 18 hours ago Alex Smart 126

0

votes

3

answers

100

views

I think you can always compress compressed data, is it true?

information-theory data-compression

modified Nov 24 at 16:21 reinierpost 2,901

5

votes

3

answers

194

views

DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$

formal-languages automata finite-automata

modified Nov 23 at 19:47 Mark Regev 38

3

votes

1

answer

459

views

In SAT, do we require an assignment for arbitrary variables?

complexity-theory reference-request satisfiability

answered Nov 24 at 19:20 Juho 15.2k

3

votes

1

answer

428

views

How binary search works in real world scenario?

algorithms search-algorithms binary-search

answered Dec 2 at 7:26 Benny Profane 96

5

votes

2

answers

102

views

Why do DFAs with a single final state have less power?

automata finite-automata computation-models

modified Dec 7 at 17:24 Apass.Jack 5,623

2

votes

2

answers

277

views

Language of all strings that has exactly 1 triple b

automata finite-automata regular-expressions

modified Dec 2 at 12:41 Mr. Sigma. 522

5

votes

2

answers

88

views

LET REC recursive expression static typing rule

programming-languages type-theory type-checking

modified 2 days ago chi 11.4k

3

votes

3

answers

85

views

Undirected graph with exponential number of simple cycles

algorithms graphs

answered yesterday David Richerby 65.3k

4

votes

2

answers

159

views

Proving a value is the result of the execution of an algorithm

proof-techniques

modified Nov 20 at 6:12 doodhwala 76

0

votes

2

answers

258

views

Clarify the steps: what happened in this mathematical modelling of TSP?

traveling-salesman notation

answered yesterday David Richerby 65.3k

3

votes

2

answers

66

views

How could a formal system ever be non-obviously unsound?

logic

modified Nov 21 at 17:46 Andrej Bauer 19.4k

4

votes

3

answers

103

views

Can we remove duplicates faster than we can sort?

time-complexity sorting hashing

modified Dec 1 at 19:12 einpoklum 312

1

vote

3

answers

66

views

Is this algorithm of constant time?

time-complexity

answered Nov 30 at 10:16 Juho 15.2k

0

votes

2

answers

39

views

When to add and when to multiply to find time complexity [closed]

algorithm-analysis

modified Nov 18 at 18:25 gnasher729 10.1k

3

votes

2

answers

54

views

Calculate the number of cycles of a Cactus graph?

graphs graph-theory

modified Dec 6 at 8:33 Juho 15.2k

1

vote

3

answers

64

views

Soundness and completeness w.r.t. programming languages

logic programming-languages type-theory

modified Dec 5 at 19:38 chi 11.4k

2

votes

1

answer

96

views

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

algorithms graphs graph-theory matching spanning-trees

modified Nov 27 at 23:59 Apass.Jack 5,623

0

votes

1

answer

255

views

Compound interest with varying compounding frequency

algorithms

modified Nov 17 at 23:52 Apass.Jack 5,623

3

votes

1

answer

66

views

Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

algorithms data-structures time-complexity

modified Dec 2 at 19:26 rici 4,300

1

vote

1

answer

107

views

Is Pattern Matching as expressive as Case Expression in Haskell?

functional-programming haskell

modified Nov 20 at 10:50 chi 11.4k

1

vote

1

answer

163

views

Define a DFA that accepts all even length binary strings that don't contain the substring “111”?

finite-automata discrete-mathematics

modified yesterday bmsh 9

4

votes

2

answers

90

views

Is there any other computation theory besides the one in automata theory?

complexity-theory formal-languages computability formal-grammars computation-models

answered Nov 28 at 17:28 André Souza Lemos 2,829

5

votes

1

answer

108

views

Find a strategy to evade hungry lions on the real line for the longest time

algorithms optimization

modified Nov 18 at 16:41 gnasher729 10.1k

2

votes

1

answer

107

views

What is the right term/theory for prediction of Binary Variables based upon their continuous value?

optimization reference-request linear-programming integer-programming

answered Dec 6 at 21:31 mhum 1,569

3

votes

2

answers

62

views

Is it possible to write a program that calculates an algorithm's time complexity? [on hold]

algorithms complexity-theory halting-problem

answered 16 hours ago Mr. Sigma. 522

1

vote

2

answers

102

views

Randomly Choosing a N-Bit Prime

number-theory probabilistic-algorithms primes

modified Nov 18 at 18:22 gnasher729 10.1k

4

votes

1

answer

79

views

Why are word sizes in modern CPU’s a power of 2?

cpu

modified Nov 25 at 11:50 user56834 1,753

5

votes

1

answer

61

views

Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

computer-architecture parallel-computing cpu performance

modified Nov 27 at 20:34 Raphael♦ 57.2k

4

votes

2

answers

46

views

Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

algorithms time-complexity selection-problem

modified Dec 2 at 17:30 Apass.Jack 5,623

3

votes

2

answers

95

views

Efficiently shuffling items in $N$ buckets using $O(N)$ space

algorithms time-complexity randomized-algorithms sampling

answered Nov 28 at 21:03 rici 4,300

2

votes

1

answer

115

views

Directed HAM Cycles with Additional Constraints to SAT

graphs reductions satisfiability

answered Dec 6 at 22:20 ConcernedCitizen 86

2

votes

1

answer

88

views

Does a Vertex Cover exist?

graphs graph-theory

answered Dec 4 at 4:52 Yuval Filmus 188k

1

vote

1

answer

106

views

If I'm just trying to show something is NP-hard (as opposed to NP-complete) does my reduction need to be completed in polynomial time?

complexity-theory

answered Nov 25 at 23:05 David Richerby 65.3k

0

votes

2

answers

49

views

Is it decidable whether one language is polytime reducible to another?

complexity-theory

answered Dec 4 at 12:47 David Richerby 65.3k

2

votes

1

answer

79

views

What is the best way to compress a string with only numbers and commas in it?

algorithms data-compression

modified Dec 6 at 8:42 Evil 7,563

0

votes

1

answer

61

views

Deleting edges such that largest connected component has at most $n/4$ nodes

complexity-theory graphs

modified Nov 21 at 15:58 Gilles♦ 32.4k

2

votes

2

answers

58

views

Proof for BFS and DFS equivalence

graph-theory graph-traversal

modified Nov 24 at 7:46 Apass.Jack 5,623

3

votes

1

answer

45

views

Do multiple transitions over the input give finite state machines more power?

formal-languages automata finite-automata

modified Nov 17 at 21:25 rici 4,300

1

vote

1

answer

92

views

How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal?

formal-languages context-free notation

modified 2 days ago rici 4,300

0

votes

1

answer

64

views

Sorting n elements in worst case of $\sqrt{n}\log n$

algorithms sorting

modified Nov 26 at 0:29 Tom Zych 202

2

votes

2

answers

63

views

Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L

automata finite-automata

modified Dec 7 at 23:37 Alfred Kaminski 16

3

votes

1

answer

60

views

Christofides algorithm (by hand)

algorithms graph-theory approximation traveling-salesman

modified Dec 5 at 15:18 Ryan Cameron 29

Top Questions

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