Theoretical Computer Science Stack Exchange

8 votes

1 answer

113 views

Halting problem with minimal Turing Machine as promised input

Edgar Daylight

5

modified 12 hours ago

5 votes

0 answers

208 views

How to prove following weighted forest problem is NP-hard?

Toyllo

51

modified 15 hours ago

0 votes

2 answers

109 views

Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?

julieb

1

modified 19 hours ago

0 votes

0 answers

50 views

Why can negating '$\Phi(G) \geq \Omega(\phi)$' be converted to '$\Phi(G) <3\phi$' in this proof instead of '$\Phi(G) < c \cdot \phi$ for all $c > 0$'?

Tyven

1

modified 19 hours ago

4 votes

1 answer

39 views

Equal appearance of positive and negative literals in 1-IN-3SAT per variable: Is it NP-complete?

Lieuwe Vinkhuijzen

2,149

answered 20 hours ago

1 vote

1 answer

71 views

+100

Can a Queue with Fewer Serves outperform a Queue with More Servers?

Lieuwe Vinkhuijzen

2,149

answered yesterday

2 votes

0 answers

134 views

"Search and Replace" Edit Distances

J..y B..y

2,786

modified yesterday

5 votes

1 answer

535 views

Is there a problem known to have no fastest algorithm, up to polynomials?

Huck Bennett

5,083

answered yesterday

0 votes

0 answers

27 views

Two-stage Robust Shortest Path Problem - worst- case second-stage of an optimal solution

Troy Troy

1

asked 2 days ago

97 votes

10 answers

20k views

What would it mean to disprove Church-Turing thesis?

ULechine

309

modified 2 days ago

-1 votes

1 answer

102 views

Is any procedure satisified by the principle of least action able to be simulated by Turing Machine?

Edgar Daylight

5

modified Sep 4 at 19:59

-1 votes

1 answer

60 views

Computing non-halting inputs of semantic non-equivalent programs

steef

9

modified Sep 4 at 9:46

-3 votes

0 answers

25 views

NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) reduction to NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) always exists?

Daniel A.

1

asked Sep 4 at 9:02

4 votes

1 answer

130 views

A potentially novel complexity measure for sets of strings

D.W.

12.3k

answered Sep 4 at 7:34

Stack Exchange Network

Explore our questions

Halting problem with minimal Turing Machine as promised input

How to prove following weighted forest problem is NP-hard?

Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?

Why can negating '$\Phi(G) \geq \Omega(\phi)$' be converted to '$\Phi(G) <3\phi$' in this proof instead of '$\Phi(G) < c \cdot \phi$ for all $c > 0$'?

Equal appearance of positive and negative literals in 1-IN-3SAT per variable: Is it NP-complete?

Can a Queue with Fewer Serves outperform a Queue with More Servers?

"Search and Replace" Edit Distances

Is there a problem known to have no fastest algorithm, up to polynomials?

Two-stage Robust Shortest Path Problem - worst- case second-stage of an optimal solution

What would it mean to disprove Church-Turing thesis?

Is any procedure satisified by the principle of least action able to be simulated by Turing Machine?

Computing non-halting inputs of semantic non-equivalent programs

NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) reduction to NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) always exists?

A potentially novel complexity measure for sets of strings

Hot Network Questions