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

0

votes

1

answer

38

views

Sat instance size and definition of TIME(f(n))

complexity-theory satisfiability polynomial-time

modified 2 hours ago Community♦ 1

4

votes

1

answer

281

views

Proving that EXP doesn't have polynomial-size circuits

complexity-theory time-complexity circuits

modified 13 hours ago xskxzr 4,841

1

vote

0

answers

20

views

Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?

complexity-theory polynomial-time-reductions

asked 20 hours ago csstundent 23

1

vote

1

answer

57

views

How to prove $L \notin \texttt{DSPACE}(f)$

complexity-theory turing-machines reductions proof-techniques space-complexity

modified yesterday Community♦ 1

1

vote

1

answer

254

views

AVL tree worst case height proof

complexity-theory binary-trees balanced-search-trees avl-trees

modified yesterday Community♦ 1

0

votes

1

answer

58

views

Modify max value multiple times of a list

algorithms complexity-theory

modified Aug 16 at 14:03 Community♦ 1

2

votes

2

answers

133

views

Circuit satisfiability problem : SAT-C to SAT-2C

complexity-theory np-complete reductions satisfiability circuits

modified Aug 16 at 13:02 Community♦ 1

0

votes

0

answers

35

views

What's the proof complexity of E-KRHyper (E-hyper tableau calculus)?

complexity-theory

asked Aug 15 at 20:30 Ricardo S. 54

2

votes

3

answers

92

views

Is the P vs NP problem, an NP or co-NP problem?

complexity-theory p-vs-np

modified Aug 15 at 14:23 J. Schmidt 143

-1

votes

0

answers

15

views

Promise problems in $NP$?

complexity-theory complexity-classes

asked Aug 15 at 8:13 Turbo 1,297

244

votes

7

answers

111k

views

What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard?

complexity-theory terminology complexity-classes p-vs-np reference-question

modified Aug 14 at 22:05 Bobby Durrett 101

3

votes

1

answer

84

views

Building maze to maximize shortest path, may be given waypoints and teleports

algorithms complexity-theory graphs algorithm-analysis

modified Aug 14 at 11:02 Community♦ 1

1

vote

1

answer

45

views

For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

complexity-theory 2-sat

modified Aug 14 at 9:03 Community♦ 1

6

votes

0

answers

206

views

Testing algorithm for a modified sieve of Eratosthenes

algorithms complexity-theory number-theory

modified Aug 13 at 0:59 Daniel Castle 141

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled