Hottest Questions This Month

5

votes

7

answers

2k

views

The running time of algorithm is at most $O(n^2)$

time-complexity asymptotics

modified Nov 2 at 15:59 Derek Allums 103

7

votes

1

answer

875

views

Is there a simple argument why graph isomorphism is not NP-complete?

modified Nov 16 at 10:55 Yuval Filmus 237k

5

votes

2

answers

821

views

Exact definition of average time complexity?

algorithms complexity-theory

modified Nov 23 at 18:05 zkutch 784

9

votes

1

answer

824

views

Monad in Haskell programming vs. Monad in category theory

programming-languages mathematical-foundations category-theory haskell

modified Nov 19 at 13:48 leftaroundabout 1,316

1

vote

1

answer

537

views

What does it mean for a grammar to be LR(0)?

formal-languages finite-automata formal-grammars compilers

modified Nov 9 at 18:27 ElidorDD 206

4

votes

2

answers

92

views

Why do OS locks require hardware support?

operating-systems threads

answered Nov 10 at 21:15 Gilles 'SO- stop being evil' 39.3k

3

votes

2

answers

67

views

Right most set bit O(log N)

algorithms bit-manipulation

answered Nov 22 at 16:29 nat nav 53

3

votes

1

answer

91

views

How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?

type-theory functional-programming fixed-point church-numerals

modified Nov 4 at 16:07 winitzki 133

1

vote

2

answers

105

views

Store a n-bit string using only O(log n) space

space-complexity hash

answered yesterday Panda Pajama 111

1

vote

1

answer

73

views

What is the diference between $\lambda x.1$ and $1$?

lambda-calculus

modified Nov 12 at 11:33 lemontree 589

4

votes

1

answer

197

views

Relationship between inductive families and type-returning functions

type-theory dependent-types agda

modified Nov 26 at 14:50 András Kovács 628

1

vote

2

answers

100

views

What does an admissible numbering of computable functions look like?

computability enumeration encoding-scheme

answered 13 hours ago Andrej Bauer 25.6k

3

votes

1

answer

95

views

Why do we need two variables for implementing kleene star operation on a language using context free grammars?

context-free kleene-star

modified Nov 3 at 14:44 chi 13.8k

1

vote

1

answer

85

views

Is there code below microcode?

computer-architecture micro-code

modified Nov 24 at 21:18 Shashank V M 386

0

votes

0

answers

172

views

Find $k$'th smallest element in matrix with sorted rows

algorithms time-complexity data-structures sorting arrays

modified Nov 20 at 18:09 user355834 1

3

votes

1

answer

57

views

Which language is used to construct a type system?

type-theory type-checking dependent-types type-inference data-flow-analysis

answered Nov 11 at 19:41 jmite 27.9k

2

votes

1

answer

73

views

How to generate a number which is divisible by all numbers in a given range?

algorithms

modified Nov 4 at 16:39 Yuval Filmus 237k

5

votes

1

answer

71

views

Number of vertices and edges lies on the boundary of bounded cells in line arrangement is O(n)

computational-geometry

modified Nov 12 at 22:03 Vladislav Bezhentsev 360

2

votes

1

answer

87

views

How to define a path between two sets of vertices?

graphs shortest-path weighted-graphs

answered 13 hours ago Yuval Filmus 237k

0

votes

2

answers

52

views

Is this possible that quantum computer will be able to violate the Church thesis?

turing-machines

modified Nov 27 at 19:54 gen 836

0

votes

1

answer

85

views

Is NP in NP/Poly?

turing-machines np nondeterminism circuits simulation

modified Nov 25 at 15:16 DeeDee 1

2

votes

2

answers

65

views

proving that a problem is in P

np p-vs-np complexity-theory

answered Nov 20 at 2:40 Bjørn Kjos-Hanssen 874

3

votes

1

answer

78

views

The difference between $\beta$-reduction and $let$

lambda-calculus

modified Nov 9 at 1:32 D.W.♦ 126k

1

vote

1

answer

77

views

Efficient algorithm for sorting objects by key that values are range from 0 to 100

sorting

modified Nov 23 at 11:41 Steven 10.7k

3

votes

2

answers

75

views

Classify an algorithm to maximize number of tips used by liquid handlers concurrently

optimization robotics

answered Nov 9 at 22:03 mhum 1,734

4

votes

1

answer

44

views

Graph coloring with fixed-size color classes

graphs optimization colorings constraint-programming

answered Nov 15 at 22:26 D.W.♦ 126k

4

votes

1

answer

72

views

Are “pipes” puzzles NP-hard?

np-hard

answered Nov 26 at 1:44 Hendrik Jan 24.2k

3

votes

1

answer

56

views

What does starvation freedom exactly mean?

operating-systems

modified Nov 2 at 6:30 Yueor 73

1

vote

2

answers

56

views

Proving some subsets of a regular languages to be regular languages

formal-languages regular-languages automata regular-expressions

answered Nov 12 at 0:44 Anazz 366

3

votes

1

answer

56

views

Kleene's Theorem and TMs

turing-machines automata finite-automata halting-problem church-turing-thesis

modified 12 hours ago Yuval Filmus 237k

0

votes

2

answers

70

views

Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?

complexity-theory dynamic-programming satisfiability 3-sat sat-solvers

modified Nov 8 at 13:14 daniel pehoushek 1

2

votes

1

answer

69

views

Deciding whether complement of context-free language is context-free

automata context-free undecidability

modified Nov 19 at 16:32 D.W.♦ 126k

2

votes

1

answer

53

views

How can I show that this language is context sensitive?

formal-languages regular-languages formal-grammars context-sensitive

modified Nov 11 at 20:47 Cheia 23

2

votes

1

answer

52

views

How were operating systems even made?

operating-systems os-kernel

answered Nov 1 at 22:17 Jörg W Mittag 2,275

1

vote

2

answers

66

views

What's the accurate definition of a compiler?

compilers

answered Nov 4 at 19:41 Victor Edebe 1

2

votes

2

answers

40

views

Irregularity of $\{0^x1^y : y \nmid x\}$

formal-languages pumping-lemma

modified Nov 10 at 22:31 Steven 10.7k

3

votes

2

answers

50

views

Cube 3x3: Using just face rotations, transform the cube from configuration A to B

algorithms

answered Nov 15 at 23:22 Pseudonym 13.6k

1

vote

1

answer

47

views

derandomize a BPP algorithm

randomized-algorithms

answered Nov 1 at 7:41 Yuval Filmus 237k

1

vote

1

answer

75

views

Connection between Pseudo random generators and hardness

complexity-theory circuits cryptography lower-bounds pseudo-random-generators

modified Nov 13 at 7:58 xskxzr 6,529

0

votes

0

answers

95

views

Proving that whether a Linear Bounded Automaton runs in polynomial time or not is undecidable

complexity-theory turing-machines linear-bounded-automata

modified Nov 25 at 0:14 dexter kozen 1

0

votes

1

answer

56

views

Describe a data structure to track visitors

data-structures

modified Nov 14 at 9:39 Steven 10.7k

2

votes

1

answer

43

views

Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$

algorithms strings randomized-algorithms hamming-distance

modified Nov 9 at 19:55 spektr 339

0

votes

0

answers

90

views

How to Show Subset Sum $\le_p$ 3-Partition

algorithms algorithm-analysis np-complete np

asked Nov 8 at 22:27 yowan60786 1

2

votes

1

answer

90

views

+50

Is occurrence typing (flow-sensitive typing) a form of dependent typing?

type-checking dependent-types

answered yesterday D.W.♦ 126k

1

vote

1

answer

54

views

Existence of particular/specialized halting oracles

turing-machines halting-problem

modified Nov 4 at 11:01 Andrej Bauer 25.6k

0

votes

2

answers

54

views

Failing to solve a recurrence by induction

complexity-theory asymptotics recurrence-relation induction

modified Nov 20 at 23:12 gnasher729 20.8k

0

votes

1

answer

42

views

Is (λx.FV(A)) and (λx.FV(B)) β-equivalent?

lambda-calculus

modified Nov 9 at 14:32 lemontree 589

2

votes

1

answer

53

views

What are the most used statements in programming (ranked)?

formal-languages regular-languages programming-languages compilers type-theory

modified Nov 4 at 6:23 Pseudonym 13.6k

Top Questions

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