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

Ask Question

more tags

Active 2 Bountied Hot Week Month

1

vote

1

answer

94

views

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

complexity-theory algorithm-analysis sorting

modified 1 hour ago gnasher729 22.9k

2

votes

1

answer

43

views

Is there a difference between extremely slow growing functions and constants with respect to computable functions?

complexity-theory polynomial-time busy-beaver

modified 11 hours ago Yuval Filmus 256k

2

votes

1

answer

17

views

Padding in proof of space hierarchy theorems

complexity-theory space-complexity

answered 22 hours ago Yuval Filmus 256k

1

vote

1

answer

29

views

Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain

complexity-theory turing-machines computability counting

modified yesterday John D 125

1

vote

1

answer

49

views

What does an NP reduction look like?

complexity-theory np

modified yesterday ruakh 236

4

votes

2

answers

106

views

tautology vs satisfiability

complexity-theory turing-machines computability reductions np

answered Jul 26 at 12:11 Highheath 525

3

votes

0

answers

30

views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

algorithms complexity-theory np-complete reductions np

modified Jul 26 at 9:24 masterHaham 213

5

votes

1

answer

79

views

Reduction from the SAT problem to the NAE-SAT problem

complexity-theory computability reductions np satisfiability

answered Jul 26 at 6:48 Shaull 15.6k

1

vote

2

answers

46

views

Reduction between CLIQUE to SUBSET SUM

complexity-theory graphs computability reductions np

modified Jul 26 at 5:47 dustyeav 181

0

votes

1

answer

59

views

Reduction from problem A to another problem B

complexity-theory computability reductions np

answered Jul 25 at 11:47 Steven 17.6k

1

vote

2

answers

112

views

Need the type of time complexity and its formula

algorithms complexity-theory time-complexity polynomial-time

answered Jul 25 at 9:30 Rostami.M 1,384

0

votes

1

answer

48

views

If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?

complexity-theory polynomial-time-reductions

modified Jul 24 at 2:04 Community♦ 1

3

votes

2

answers

50

views

Reduction with CoNP and CoNPC

complexity-theory computability np-complete reductions np

answered Jul 23 at 20:02 Arno 1,684

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled