Hottest Questions This Month

22

votes

7

answers

5k

views

Given a specific computer system, is it possible to estimate the actual precise run time of a piece of Assembly code

assembly

modified Sep 3 at 16:24 Davislor 963

29

votes

2

answers

1k

views

Planar regular languages

modified Sep 12 at 22:05 Hendrik Jan 22.4k

5

votes

2

answers

1k

views

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

graphs turing-machines space-complexity

modified 2 days ago Nayuki 563

9

votes

1

answer

1k

views

Why does Coq include let-expressions in its core language

type-theory dependent-types type-checking coq

modified Sep 11 at 19:24 Andrej Bauer 22.3k

3

votes

2

answers

828

views

Finding square root without division and initial guess [closed]

algorithms

answered Aug 27 at 8:36 gnasher729 14.7k

7

votes

1

answer

591

views

Random restarts for unsatisfiable instances

satisfiability randomized-algorithms 3-sat sat-solvers

modified Sep 16 at 9:12 David Richerby 75.3k

4

votes

2

answers

160

views

Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

asymptotics

modified Aug 29 at 13:57 Doc Brown 163

4

votes

1

answer

115

views

Why are struct and class essentially the same in C++?

history language-design c++

modified Sep 3 at 3:06 HEKTO 1,711

0

votes

5

answers

76

views

How does the computer know whether an address contains an instruction to be executed, or data to be used in an instruction?

computer-architecture

answered Sep 7 at 13:23 gnasher729 14.7k

3

votes

1

answer

203

views

Basic Theta-notation question

asymptotics

answered Aug 23 at 8:13 dkaeae 4,535

3

votes

3

answers

92

views

Is it possible to have high compression but low predictability?

complexity-theory information-theory data-compression

modified Sep 16 at 13:25 Oleg Dats 133

1

vote

2

answers

90

views

Can we always transform a set of lines to a function?

programming-languages functional-programming

modified Sep 5 at 5:20 Nishant 120

1

vote

3

answers

62

views

How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

computer-architecture recursion

modified Sep 17 at 16:25 gandalf61 593

6

votes

1

answer

49

views

Perpendicular vectors out of a set

optimization computational-geometry

modified Sep 11 at 14:55 xskxzr 5,082

3

votes

1

answer

103

views

Are these 2 equivalent?

logic discrete-mathematics propositional-logic

answered Sep 8 at 14:53 Yuval Filmus 208k

1

vote

1

answer

62

views

On $L^* - \{\epsilon\} = L^+$

automata equality

answered Aug 30 at 13:26 Yuval Filmus 208k

4

votes

1

answer

61

views

Is DISCRETE LOG a NP hard problem?

complexity-classes

modified Aug 28 at 7:20 D.W.♦ 106k

2

votes

2

answers

60

views

How to prove NP-hardness from scratch?

complexity-theory reductions np-hard

modified 7 hours ago David Richerby 75.3k

1

vote

2

answers

119

views

Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?

graphs np-complete reductions

modified Aug 26 at 7:04 Thinh D. Nguyen 1,817

0

votes

2

answers

142

views

Let L be any non-empty language over an alphabet Σ. Show that $L^2$ ⊆ $L^3$ if and only if λ ∈ L

formal-languages

answered yesterday gnasher729 14.7k

2

votes

2

answers

85

views

Algorithm to count the number of subsets of size k with sum of all its elements minimum possible

combinatorics

answered Sep 8 at 16:37 Yuval Filmus 208k

-1

votes

1

answer

49

views

Why is it not possible to prove that two Turing Machines calculate the same function?

formal-languages turing-machines undecidability halting-problem

modified Sep 17 at 20:07 Andrej Bauer 22.3k

1

vote

3

answers

74

views

Why is heap insert O(logN) instead O(n) when you use an array?

data-structures arrays heaps big-o-notation

answered Sep 8 at 11:09 gnasher729 14.7k

4

votes

1

answer

69

views

Exact meaning of $2^{\mathcal{O}(f(n))}$

complexity-theory asymptotics notation big-o-notation

modified Sep 4 at 17:38 Dan 23

-2

votes

2

answers

65

views

Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?

algorithms np-complete shortest-path np traveling-salesman

answered Sep 18 at 5:40 Peter Taylor 1,583

1

vote

4

answers

64

views

How does a computer compute negative(-) and positive(+) Infinity?

arithmetic floating-point number-formats

answered Sep 5 at 23:28 David Richerby 75.3k

1

vote

1

answer

60

views

Concrete example of Vertex Cover to Subset Sum reduction

np-complete reductions polynomial-time-reductions

answered 21 hours ago David Richerby 75.3k

3

votes

1

answer

97

views

Distinct Binary Heaps

algorithms binary-trees recursion heaps

answered Sep 19 at 0:26 Christopher Boo 318

3

votes

1

answer

58

views

Linear programs with strict inequalities and supremum objectives

linear-programming

answered Aug 23 at 13:16 Yuval Filmus 208k

1

vote

1

answer

44

views

How can $A \cup B$ be decidable if $B$ is undecidable?

turing-machines undecidability sets

answered Sep 16 at 11:03 David Richerby 75.3k

3

votes

1

answer

56

views

k-disjoint pair paths where any source can pair with any sink

algorithms graphs graph-theory

modified Aug 29 at 23:47 inspuration 18

0

votes

1

answer

56

views

Why are ADT packages opened immediately after they are built, while existential objects opened as late as possible?

programming-languages type-theory polymorphisms

answered Sep 7 at 0:06 Ptival 171

4

votes

0

answers

116

views

Is this equivalent to any famous NP-complete problem?

complexity-theory graph-theory np-complete

modified Sep 14 at 17:19 J.E.C. 21

3

votes

1

answer

41

views

Is this lambda abstraction created as a generator of a recursive function?

lambda-calculus recursion

modified Aug 29 at 7:29 dkaeae 4,535

0

votes

3

answers

67

views

How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$

algorithms runtime-analysis big-o-notation

answered 2 days ago gnasher729 14.7k

1

vote

2

answers

67

views

Since the halting problem is undecidable, does that mean that there exists an always undecidable program?

turing-machines undecidability halting-problem

answered Sep 3 at 18:52 Draconis 6,327

0

votes

1

answer

65

views

Are computers infallible?

turing-machines

answered Sep 9 at 16:27 gandalf61 593

1

vote

1

answer

39

views

Counting common values in two arrays

time-complexity arrays

modified Aug 25 at 22:23 Yuval Filmus 208k

2

votes

1

answer

49

views

Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

master-theorem

answered Aug 23 at 18:26 Tassle 606

2

votes

2

answers

38

views

DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$

context-free pushdown-automata

modified Aug 29 at 13:49 Yuval Filmus 208k

3

votes

1

answer

61

views

Algorithm to find a simple path with maximum weight less than a constant in DAG

algorithms complexity-theory graphs graph-theory np-hard

modified Sep 14 at 5:57 xskxzr 5,082

2

votes

1

answer

60

views

Why is LinkedList useful?

data-structures arrays linked-lists

answered Sep 10 at 11:26 harold 908

1

vote

1

answer

77

views

Elementary proof that Bool is a Set

homotopy-type-theory

answered Sep 1 at 4:53 Dan Doel 946

3

votes

1

answer

36

views

Proof of sparsification lemma: What exactly does the $\pi$ operator do?

complexity-theory sets

answered Aug 24 at 17:00 Tassle 606

3

votes

1

answer

76

views

Minimum Path cover in a Directed Acyclic Graph

algorithms complexity-theory graphs weighted-graphs hamiltonian-path

answered Sep 11 at 16:43 xskxzr 5,082

2

votes

1

answer

59

views

Algorithm to find longest path in a tree that is smaller than x

dynamic-programming shortest-path binary-trees

modified Sep 18 at 8:16 Max 11

4

votes

1

answer

58

views

Proving with co-induction principles

proof-techniques formal-methods coq coinduction

answered Sep 16 at 9:22 Derek Elkins 11.2k

0

votes

1

answer

55

views

Do the following concepts belong to syntax or semantics?

programming-languages type-theory semantics syntax

modified Sep 2 at 6:04 Andrej Bauer 22.3k

Top Questions

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