Hottest Questions This Week

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

4

votes

1

answer

196

views

Relationship between inductive families and type-returning functions

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 10 hours ago Andrej Bauer 25.6k

0

votes

2

answers

52

views

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

turing-machines

modified 2 days ago 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

1

answer

74

views

How to define a path between two sets of vertices?

graphs shortest-path weighted-graphs

answered 9 hours ago Yuval Filmus 237k

3

votes

1

answer

52

views

Kleene's Theorem and TMs

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

modified 9 hours ago Yuval Filmus 237k

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

41

views

any one can prove following inequality?

discrete-mathematics

answered Nov 26 at 10:29 Steven 10.7k

1

vote

2

answers

47

views

Solving T(n) = 2*T(n-1)+4 witht the Master Theorem

time-complexity master-theorem

answered yesterday Yuval Filmus 237k

-3

votes

0

answers

74

views

Consider the game move the block slide puzzle [closed]

algorithms algorithm-analysis sorting artificial-intelligence

asked Nov 27 at 6:15 taimoor khan 1

2

votes

1

answer

42

views

Can one find an algorithm whose running time is larger than Ackermann's function?

runtime-analysis

answered Nov 25 at 13:14 Steven 10.7k

0

votes

2

answers

49

views

Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$

recurrence-relation check-my-answer

answered Nov 26 at 15:19 plop 636

1

vote

0

answers

62

views

Minimum cost problem of breaking containers in $O(n\log n)$

algorithms

modified yesterday Yuval Filmus 237k

0

votes

0

answers

60

views

Distribution Sort - Split elements

algorithms sorting

modified Nov 27 at 17:20 Maria Zak 11

1

vote

0

answers

56

views

Unordered data structure with fast insertion, deletion, and iteration

data-structures c++

modified Nov 26 at 14:40 lisyarus 121

0

votes

1

answer

25

views

Beta reduction of S combinator in pure lambda calculus

lambda-calculus combinatory-logic

modified 10 hours ago Andrej Bauer 25.6k

1

vote

1

answer

38

views

Can you build a solver from a verifier?

turing-machines data-compression semi-decidability

modified Nov 25 at 20:42 DeeDee 1

0

votes

1

answer

37

views

Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$

formal-languages finite-automata

answered Nov 24 at 13:17 Luke Mathieson 17.1k

0

votes

0

answers

47

views

Is this set Recursive or Recursively Enumerable?

computability undecidability sets

modified Nov 24 at 12:12 Hybrid_Thinker 1

2

votes

1

answer

36

views

Prove that ${NP}^{NP}=\Sigma_2$

complexity-theory

answered yesterday Yuval Filmus 237k

-3

votes

0

answers

46

views

Design a algorithm of graph

algorithms graphs breadth-first-search

asked Nov 25 at 9:31 pin 1

1

vote

1

answer

46

views

Showing that $F$ is a monotone function

partial-order data-flow-analysis lattices order-theory

answered Nov 26 at 15:36 Yuval Filmus 237k

2

votes

1

answer

34

views

2-Approximation algorithm for for messages across a cyclic network

graphs approximation randomized-algorithms greedy-algorithms

answered Nov 26 at 22:25 Yuval Filmus 237k

1

vote

1

answer

26

views

Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$

asymptotics master-theorem

modified 7 hours ago Steven 10.7k

0

votes

0

answers

41

views

Implications in $\mathbb{NP}$-completeness

complexity-theory np-complete np polynomial-time

modified Nov 25 at 16:01 ball_jan 1

0

votes

1

answer

40

views

How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit?

bit-manipulation

modified 50 mins ago zkutch 784

1

vote

1

answer

24

views

Enumeration of BPP machines

complexity-theory turing-machines

answered 10 hours ago Yuval Filmus 237k

1

vote

1

answer

29

views

Average of all sums of subarrays

algorithms time-complexity data-structures

modified Nov 26 at 21:24 Yuval Filmus 237k

1

vote

0

answers

37

views

How do I compress data vectors in broadcast messages?

data-structures computer-networks data-compression encoding-scheme

modified Nov 24 at 20:12 fhm 21

0

votes

0

answers

37

views

+50

Analysis of updating vertex and one example?

algorithms graphs data-structures trees shortest-path

modified yesterday Davied Zuhraph 51

1

vote

1

answer

36

views

Height of AVL tree with balance condition of 2

binary-trees discrete-mathematics

answered Nov 25 at 4:46 Pseudonym 13.6k

1

vote

1

answer

36

views

Second chance binpacking register allocator

compilers

modified 8 hours ago zagortenay333 111

0

votes

1

answer

35

views

Time complexity of $a^{n^b}; a,b>1$

time-complexity

modified Nov 27 at 15:09 David H 3

1

vote

1

answer

27

views

Inductive proof for Euclid's algorithm

algorithms

answered 2 days ago Yuval Filmus 237k

1

vote

1

answer

26

views

Inductive proof for the Bubblesort algorithm

algorithms

answered Nov 25 at 6:28 CSSTUDENT 151

0

votes

1

answer

26

views

Linear programming reduce errors

algorithms linear-programming

modified 17 hours ago D.W.♦ 126k

2

votes

0

answers

33

views

Relationship between dynamic programming and reinforcement learning

dynamic-programming reinforcement-learning

modified Nov 25 at 13:29 quest ions 21

0

votes

1

answer

33

views

Cannot determine if this language is context-free or not

finite-automata context-free

answered Nov 26 at 4:54 Bhavani Prasad 1

0

votes

0

answers

33

views

External Sorting - Calculate passes with different number of disks

algorithms database-theory databases mergesort

modified Nov 24 at 17:53 Maria Zak 11

1

vote

1

answer

20

views

Why $((+ 1) ((+ 1) 1))$ is not a $\delta-$redex?

lambda-calculus

modified 20 hours ago lemontree 589

1

vote

1

answer

25

views

Strengthening a given attack on discrete log

cryptography number-theory group-theory

modified 5 hours ago Yuval Filmus 237k

0

votes

2

answers

32

views

Describe a turing machine that accepts Language L = {www| w is {a,b}*}

turing-machines

answered Nov 24 at 0:13 Hybrid_Thinker 1

2

votes

1

answer

23

views

Min weighted edge cover - is the greedy algorithm sub-optimal?

graphs optimization combinatorics

modified 2 days ago Rohit Pandey 209

1

vote

2

answers

29

views

Two-Sum - Range Allowance Algorithm Design

algorithms algorithm-analysis dynamic-programming hash-tables pseudocode

answered 12 hours ago D.W.♦ 126k

1

vote

1

answer

22

views

Time estimation for successful brute force attack

cryptography

answered Nov 25 at 18:46 kelalaka 837

0

votes

2

answers

17

views

PRECISE DPLL algorithm definition

algorithms definitions

answered yesterday Pseudonym 13.6k

Top Questions

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