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 4 Bountied Hot Week Month

2

votes

1

answer

77

views

How to prove LastToken problem is NP-complete

complexity-theory np-complete decision-problem

modified 7 hours ago narek Bojikian 2,210

1

vote

0

answers

9

views

Proof that $(L_{all})^C$ is not recursively enumerable

complexity-theory turing-machines

modified 8 hours ago David 11

8

votes

1

answer

190

views

is $P_{CTC} = BPP_{path}$?

complexity-theory complexity-classes quantum-computing

modified 12 hours ago Community♦ 1

1

vote

1

answer

31

views

Algorithm for idempotent algebra

complexity-theory np-complete boolean-algebra oracles

modified 12 hours ago D.W.♦ 112k

2

votes

1

answer

41

views

Finding a vertex coverage that is also an independent set

algorithms complexity-theory graphs np-complete

modified yesterday narek Bojikian 2,210

1

vote

1

answer

41

views

Proving NP-Complete problem by reduction of subset-sum

complexity-theory reductions

modified yesterday narek Bojikian 2,210

-1

votes

1

answer

22

views

Another Subset sum problem

complexity-theory np-complete np-hard np

answered yesterday Yuval Filmus 214k

1

vote

1

answer

48

views

Question about how can i determine if counting sort is the right option over other sorting algorithms

complexity-theory algorithm-analysis sorting

modified yesterday Community♦ 1

1

vote

1

answer

23

views

Subset sum to 0/1 knapsack

algorithms complexity-theory np-complete np-hard np

answered 2 days ago narek Bojikian 2,210

2

votes

2

answers

161

views

Polynomial bound on sum of strings

complexity-theory discrete-mathematics

answered 2 days ago eatfood 143

1

vote

1

answer

107

views

How do I reduce subset sum to another problem in NP?

algorithms complexity-theory reductions np-hard

modified Dec 5 at 5:36 Juho 18.1k

5

votes

3

answers

137

views

Is there any other computation theory besides the one in automata theory?

complexity-theory formal-languages computability formal-grammars computation-models

modified Dec 4 at 19:32 Yos 21

0

votes

0

answers

34

views

Restriction: polynomial time decision of instance is why needed to “decision Problem”?

complexity-theory computability decision-problem

asked Dec 4 at 7:14 y y 1

0

votes

0

answers

7

views

why is the NL solution PATH negated unsufficient to prove unreachability

complexity-theory

Dec 4 at 5:39

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled