Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

more tags

Active 2 Bountied Hot Week Month

7

votes

0

answers

87

views

Are weakly polynomial time algorithms truly polynomial?

algorithms complexity-theory turing-machines computation-models

modified 4 hours ago padawan 1,369

27

votes

6

answers

5k

views

Is there a physical analogy to the Turing Machine?

turing-machines computation-models

modified 7 hours ago reinierpost 3,620

0

votes

0

answers

36

views

Show that for every language A, there exists a language B such that not B ≤m A

complexity-theory turing-machines

modified 8 hours ago John 1

2

votes

1

answer

30

views

Composition of functions computable in logspace

complexity-theory turing-machines space-complexity

answered 12 hours ago Yuval Filmus 217k

2

votes

1

answer

68

views

Prove {<M> | TM M on input 3 at some point writes symbol “3” on the third cell of its tape} is recursively enumerable but not recursive

formal-languages turing-machines computability regular-languages undecidability

answered yesterday hh vh 317

2

votes

1

answer

67

views

Maximum number of steps a Turing machine makes

turing-machines

answered 2 days ago vonbrand 10.1k

-1

votes

0

answers

45

views

Prove that for any non empty Σ show that there exists language that are not recursively enumerable

turing-machines

asked Feb 21 at 11:21 Bro 1

0

votes

1

answer

19

views

simple question about epsilon and estimation turing machines

complexity-theory turing-machines computability optimization

answered Feb 17 at 14:41 GoodDeeds 843

1

vote

1

answer

30

views

What are HP and MP in this context?

turing-machines computability automata

answered Feb 16 at 22:22 Rick Decker 13.5k

-1

votes

0

answers

19

views

algorithm for a #SAT oracle (#SAT algorithm)

complexity-theory turing-machines computability satisfiability counting

asked Feb 16 at 20:21 satologic 1

2

votes

1

answer

80

views

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

turing-machines computability automata

modified Feb 16 at 16:02 Community♦ 1

1

vote

1

answer

46

views

Connection between vertex cover and P=NP

complexity-theory turing-machines computability np-hard vertex-cover

modified Feb 16 at 14:23 STanja 136

0

votes

1

answer

16

views

Reducing vertex cover to minimal vertex cover

complexity-theory turing-machines computability reductions vertex-cover

answered Feb 16 at 1:54 vonbrand 10.1k

2

votes

1

answer

590

views

Is chess game movement TM decidable?

turing-machines automata undecidability decision-problem

modified Feb 14 at 20:02 Mateusz Piotrowski 303

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled