The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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

1

vote

1

answer

33

views

Converting a greedy algorithm to a dynamic programming algorithm

complexity-theory graphs dynamic-programming greedy-algorithms divide-and-conquer

modified 4 hours ago narek Bojikian 655

3

votes

1

answer

71

views

High-dimensional geometry and P vs. NP

complexity-theory computational-geometry satisfiability

answered yesterday Zirui Wang 377

1

vote

1

answer

45

views

Variant of stCON

complexity-theory graphs

modified 2 days ago Community♦ 1

4

votes

4

answers

2k

views

Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

complexity-theory machine-learning np knapsack-problems

answered 2 days ago Vincenzo 2,389

3

votes

2

answers

39

views

How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

complexity-theory asymptotics

answered Oct 19 at 11:12 Alex R 38

1

vote

1

answer

25

views

Find a truth assignment of 2SAT that has the most number of true variables?

complexity-theory np-complete satisfiability

answered Oct 17 at 20:19 Yuval Filmus 210k

0

votes

0

answers

17

views

Do problems that have unary encodings automatically become unary languages?

complexity-theory time-complexity runtime-analysis

asked Oct 16 at 20:23 KKP 1

249

votes

7

answers

113k

views

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

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

modified Oct 16 at 11:04 xskxzr 5,340

19

votes

7

answers

3k

views

Would proving P≠NP be harder than proving P=NP?

complexity-theory p-vs-np

answered Oct 16 at 8:28 gnasher729 15k

4

votes

1

answer

67

views

Are SAT problems with at most one false clause NP-complete?

complexity-theory np-complete satisfiability

answered Oct 15 at 6:36 xskxzr 5,340

1

vote

1

answer

29

views

If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?

complexity-theory complexity-classes

modified Oct 13 at 22:24 RandomPerfectHashFunction 441

3

votes

1

answer

25

views

Does there exist any unrelativized separation between a quantum complexity class and a classical one?

complexity-theory quantum-computing oracle-machines

answered Oct 13 at 17:52 Robert Andrews 325

19

votes

2

answers

2k

views

Subset Sum: reduce special to general case

complexity-theory reductions np-hard

answered Oct 13 at 16:16 j_random_hacker 3,187

1

vote

2

answers

43

views

Proof with induction even number of letter

complexity-theory computability

answered Oct 13 at 11:59 gnasher729 15k

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled