Hottest Questions This Week

2

votes

1

answer

227

views

The meaning and relevance of the locution ''no terminating implementation'' in type theory

modified yesterday Andrej Bauer 24.8k

1

vote

1

answer

205

views

How to understand quantifier without predication “ ∀(λφ. (φ x m→ φ y))”?

modified 11 hours ago Andrej Bauer 24.8k

3

votes

2

answers

95

views

Is it possible to construct a finite state automata for a decimal adder?

formal-languages finite-automata

answered 2 days ago J.-E. Pin 5,353

-1

votes

3

answers

136

views

Why don't passwords prove P != NP?

np-complete decision-problem complexity-classes p-vs-np

answered 2 days ago Richie Yeung 111

2

votes

1

answer

76

views

Complexity of specific cases of MAX2SAT

complexity-theory np-complete reductions satisfiability 2-sat

modified Aug 10 at 0:58 Ari 1,587

0

votes

1

answer

71

views

Minimum number of given operations in order to group letters in a string

algorithms dynamic-programming search-algorithms strings

modified yesterday John L. 23.6k

2

votes

1

answer

83

views

Is this a known problem in graph theory?

graphs weighted-graphs set-cover

modified yesterday plop 422

0

votes

3

answers

39

views

How does the OS handle multiple stacks in its physical memory?

operating-systems memory-management virtual-memory stacks

answered Aug 10 at 7:13 Martin Kochanski 1,014

1

vote

2

answers

46

views

Can User Level Thread read/write Kernel thread?

operating-systems threads os-kernel

answered 2 days ago D.W.♦ 123k

1

vote

2

answers

62

views

How to express a type that represents an associative array whose keys determine the type of the value?

type-theory dependent-types

answered Aug 9 at 20:20 Andrej Bauer 24.8k

1

vote

1

answer

57

views

When and Why do I Rehash?

algorithms hash

modified Aug 10 at 8:59 Ariel 11.6k

0

votes

1

answer

84

views

Set difference of recursively enumerable language and regular language

formal-languages turing-machines computability regular-languages context-free

answered yesterday Noah Schweber 1,866

0

votes

1

answer

61

views

Algorithmic problem of regular, context-free, and recursively enumerable languages

formal-languages turing-machines regular-languages context-free undecidability

answered 22 hours ago plshelp 402

2

votes

1

answer

69

views

Calculate the area of the shape created by multiple paths

algorithms computational-geometry

modified 2 days ago D.W.♦ 123k

0

votes

1

answer

68

views

building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

regular-languages finite-automata

answered Aug 8 at 12:40 gnasher729 19.6k

2

votes

1

answer

51

views

Probability of winning a turn-based game with a random element

dynamic-programming probability-theory

answered yesterday Watercrystal 351

0

votes

1

answer

38

views

For an NFA, can we always find a RAM?

complexity-theory formal-languages computability finite-automata discrete-mathematics

answered Aug 10 at 0:20 vonbrand 12k

1

vote

1

answer

59

views

Dataset of Hard Instances of SUBSET-SUM

subset-sum

modified 16 hours ago D.W.♦ 123k

1

vote

2

answers

35

views

Can lists be defined in a special way so that they contain things of different type?

lambda-calculus functional-programming category-theory

modified 8 mins ago D.W.♦ 123k

1

vote

2

answers

43

views

What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

complexity-theory time-complexity complexity-classes space-complexity

answered Aug 8 at 21:55 Dmitry 1,012

2

votes

1

answer

43

views

Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?

complexity-theory complexity-classes

answered 2 days ago Ariel 11.6k

2

votes

0

answers

53

views

Enumerating points on the integer lattice, within a sphere, sorted by angle, in O(1) space

computational-geometry space-complexity

modified Aug 11 at 17:18 Jeffrey 206

0

votes

1

answer

41

views

Find Index In Sorted Array Such That A[i] = C1 * i + C2

algorithms binary-search

answered Aug 7 at 21:44 gnasher729 19.6k

2

votes

0

answers

50

views

(Co)-monads and terminating implementations

lambda-calculus type-theory category-theory

modified 8 hours ago user65526 194

0

votes

1

answer

38

views

change turing machine to RAM

formal-languages turing-machines computability church-turing-thesis

modified yesterday J.-E. Pin 5,353

-2

votes

1

answer

38

views

running RAM on a given input

complexity-theory turing-machines computability finite-automata church-turing-thesis

answered Aug 11 at 2:21 vonbrand 12k

0

votes

1

answer

38

views

Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

undecidability decision-problem semi-decidability

modified Aug 11 at 6:22 Kai 362

0

votes

0

answers

48

views

How do type classes make ad-hoc polymorphism less ad hoc?

type-theory haskell abstract-data-types

modified Aug 11 at 11:13 Max Heiber 183

0

votes

1

answer

36

views

Why is this language not pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

formal-languages context-free pumping-lemma

modified Aug 11 at 6:22 greybeard 687

0

votes

1

answer

46

views

Does DFS have better constants/complexity than Backtracking on a Graph?

graphs time-complexity graph-traversal backtracking depth-first-search

answered 2 days ago Optidad 1,251

0

votes

0

answers

45

views

Why did Hopcroft and Karp write $M_0, M_1, M_2, \cdots, M_i, \cdots$? (Hopcroft - Karp Algorithm)

graphs matching bipartite-matching

asked Aug 10 at 2:01 tchappy ha 111

0

votes

1

answer

35

views

Complete proof of PAC learning of axis-aligned rectangles

machine-learning

answered Aug 10 at 8:35 Ariel 11.6k

3

votes

1

answer

35

views

Is MAX-averageSAT a well-known problem?

optimization np-complete satisfiability 3-sat maxsat

answered Aug 9 at 18:51 D.W.♦ 123k

0

votes

1

answer

35

views

Is it incorrect too say that this function problem cannot be in $FNP$?

np nondeterminism

modified 12 mins ago D.W.♦ 123k

-1

votes

0

answers

44

views

Determining algorithmically decidable or not [duplicate]

turing-machines undecidability

asked yesterday David Jenkins 1

0

votes

1

answer

42

views

Algorithm to find all connected objects

algorithms

answered Aug 11 at 7:54 Jonas 1

0

votes

1

answer

32

views

Approximate bin-packing?

algorithms combinatorics packing

modified 19 hours ago platypus17 1

0

votes

1

answer

32

views

social network analysis - relations between people with weights

algorithms graphs

modified Aug 9 at 16:10 Tassle 1,442

-1

votes

1

answer

41

views

From Python to Java or C++? [closed]

programming-languages

answered Aug 8 at 17:41 user125274 1

0

votes

0

answers

41

views

Is $x$ in the working range [3,2]?

floating-point binary

asked Aug 10 at 11:07 codelearner 1

0

votes

1

answer

40

views

PageRank vector

data-mining

answered 2 days ago jm jm 21

0

votes

0

answers

38

views

The class of grammars recognizable by backtracking recursive-descent parsers

formal-languages context-free pushdown-automata parsers backtracking

modified Aug 8 at 10:23 user35443 203

-1

votes

2

answers

29

views

When is Huffman code the most unoptimal?

huffman-coding

modified 16 hours ago Pseudonym 12.6k

1

vote

1

answer

27

views

Union of every language within group of decidable languages is also decidable?

undecidability halting-problem finite-sets

answered Aug 10 at 16:42 Gilles 'SO- stop being evil' 38.7k

0

votes

1

answer

34

views

How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length?

pumping-lemma

answered Aug 10 at 0:13 vonbrand 12k

-3

votes

0

answers

34

views

Express L(G) in set notation

context-free formal-grammars

modified Aug 10 at 18:15 D.W.♦ 123k

0

votes

0

answers

33

views

Why do we need MinHeap for Meeting Rooms 2 Leetcode problem

algorithms sorting arrays heaps

modified Aug 9 at 17:55 Umer Farooq 113

Top Questions

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