Hottest Questions Today

1

vote

1

answer

11

views

Determining the intersections of a line segment and grid

answered 2 hours ago D.W.♦ 126k

0

votes

0

answers

23

views

What does this mysterious code do?

algorithms

asked 8 hours ago joyusbro 11

0

votes

0

answers

15

views

Regular language, CFG and LL(k)

automata regular-languages context-free formal-grammars pushdown-automata

modified 4 hours ago automatontheory 1

0

votes

0

answers

23

views

NP-Complete Upper bounded partition problem

complexity-theory reductions np partitions subset-sum

asked 12 hours ago tensentinton 1

2

votes

0

answers

12

views

Separating labelled points with a plane, minimizing label variance

optimization statistics clustering

modified 10 hours ago orlp 9,981

1

vote

0

answers

25

views

The word “algebra” in category theory

functional-programming category-theory algebra

asked 14 hours ago thoughtpolice 51

0

votes

0

answers

23

views

Show that this language is undecidable

turing-machines undecidability discrete-mathematics

modified 10 hours ago codetime 111

1

vote

0

answers

31

views

Can you build a solver circuit from a verifier circuit?

circuits

modified 16 hours ago Community♦ 1

0

votes

0

answers

18

views

Can you build a solver for a language from a solver for its complement?

turing-machines semi-decidability

asked 16 hours ago Community♦ 1

0

votes

0

answers

18

views

answers Average case analysis of linear search

time-complexity algorithm-analysis runtime-analysis

asked 15 hours ago ErroR 47

0

votes

0

answers

22

views

Proof CFG defines regular language but is not LL(k)

automata regular-languages finite-automata context-free pushdown-automata

modified 5 hours ago automatontheory 1

0

votes

1

answer

19

views

Why is this implementation of the hash function bad?

hash hash-tables

modified 18 hours ago Alexey Romanov 3,017

1

vote

1

answer

49

views

Return 3 smallest elements in a list

algorithms

modified 19 hours ago Sepehr Omidvar 171

0

votes

0

answers

13

views

Bad data for hash function

hash hash-tables

asked 18 hours ago Kapa 155

-1

votes

0

answers

15

views

Intern assigning problem with maximum bipartite matching

graphs network-flow bipartite-matching bipartite-graph

asked 20 hours ago rlo.ldl 1

0

votes

0

answers

12

views

Using vector clocks vs. directed acyclic graph for causality detection in distributed systems

distributed-systems dag

asked 20 hours ago Gerard Yin 101

0

votes

0

answers

15

views

Prove that for any finite k = 1, 2, 3 … PCPk is decidable

complexity-theory mathematical-foundations

asked 21 hours ago wheat 1

3

votes

1

answer

32

views

Under which conditions a given program is deterministic on x86_64 machines?

computer-architecture randomness cpu

answered 23 hours ago D.W.♦ 126k

0

votes

0

answers

14

views

What is the contradiction in the proof of the halting theorem?

turing-machines halting-problem

modified 22 hours ago user2277550 181

0

votes

1

answer

21

views

Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard

algorithms complexity-theory reductions cryptography

answered 22 hours ago Ariel 11.8k

0

votes

1

answer

63

views

P≠NP, yet NP=co-NP

complexity-theory np

modified yesterday Noah Schweber 1,984

0

votes

1

answer

27

views

What is the difference between Big O and asymptotic notation?

algorithms complexity-theory time-complexity

modified yesterday zkutch 784

0

votes

0

answers

20

views

The minimum three elements from two tuples of size 3

algorithms

asked yesterday joyusbro 11

0

votes

0

answers

28

views

How to find best location for administration building to cover most communications between other buildings?

graphs graph-traversal python

modified yesterday Aras 101

2

votes

1

answer

97

views

How to define a path between two sets of vertices?

graphs shortest-path weighted-graphs

answered 2 days ago Yuval Filmus 237k

1

vote

2

answers

104

views

What does an admissible numbering of computable functions look like?

computability enumeration encoding-scheme

answered 2 days ago Andrej Bauer 25.6k

-1

votes

0

answers

20

views

Given a three-way set associative cache with 4 sets. Each block has two words. Use LRU replacement. Fill in the following table

cache

asked yesterday Dylan Cody 1

3

votes

1

answer

67

views

Kleene's Theorem and TMs

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

modified 2 days ago Yuval Filmus 237k

-1

votes

0

answers

19

views

Can anyone help me with these problems? [closed]

recursion

asked yesterday jamestaylor 1

0

votes

0

answers

18

views

TM that it's Language is only 10 words

turing-machines

asked yesterday Yuki1112 1

0

votes

1

answer

21

views

Can anyone tell me why this search parition for quicksort works?

algorithms

answered yesterday Sneftel 155

1

vote

1

answer

44

views

How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?

turing-machines discrete-mathematics semi-decidability

modified 6 hours ago John L. 24.1k

1

vote

1

answer

26

views

Enumeration of BPP machines

complexity-theory turing-machines

answered 2 days ago Yuval Filmus 237k

0

votes

2

answers

37

views

Linear programming reduce errors

algorithms linear-programming

answered 9 hours ago gnasher729 20.8k

1

vote

0

answers

20

views

Time hierarchy theorem for BPTIME

complexity-theory turing-machines

asked yesterday BlackHat18 263

1

vote

1

answer

30

views

Strengthening a given attack on discrete log

cryptography number-theory group-theory

modified yesterday Yuval Filmus 237k

-1

votes

0

answers

13

views

How can I shove that L is not regular in the language [duplicate]

algorithms automata pumping-lemma

modified 1 hour ago D.W.♦ 126k

1

vote

1

answer

27

views

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

asymptotics master-theorem

modified yesterday Steven 10.7k

0

votes

0

answers

14

views

Trying to figure out the best way to approach this problem with Computer Vision

machine-learning computer-vision image-processing comparison digital-image-processing

modified yesterday bumblyboi 1

1

vote

2

answers

50

views

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

time-complexity master-theorem

answered 2 days ago Yuval Filmus 237k

1

vote

1

answer

14

views

Optimal way to pack items with multidimensional weight such that the number of items is minimized?

algorithms knapsack-problems packing

modified yesterday D.W.♦ 126k

-2

votes

0

answers

28

views

Dijkstra's algorithm using Fibonacci heap

algorithms graphs

asked 2 days ago Paul 1

1

vote

1

answer

20

views

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

lambda-calculus

modified 2 days ago lemontree 589

2

votes

1

answer

40

views

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

complexity-theory

answered 2 days ago Yuval Filmus 237k

1

vote

0

answers

12

views

Tracking approximate values of specific percentiles

algorithms statistics

asked 2 days ago synapse 111

0

votes

1

answer

25

views

Beta reduction of S combinator in pure lambda calculus

lambda-calculus combinatory-logic

modified 2 days ago Andrej Bauer 25.6k

0

votes

1

answer

19

views

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

time-complexity runtime-analysis recurrence-relation recursion induction

modified 2 days ago Steven 10.7k

-2

votes

0

answers

24

views

Is it true that a Log Space Transducer's output uses polynomial space? Why or Why not?

complexity-theory turing-machines reductions polynomial-time

asked 2 days ago Amy 1

Top Questions

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