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

21

views

NP-hard or not: two partition with finite irrational input

complexity-theory np-hard

modified 1 hour ago Throckmorton 730

7

votes

0

answers

87

views

Are weakly polynomial time algorithms truly polynomial?

algorithms complexity-theory turing-machines computation-models

modified 4 hours ago padawan 1,369

2

votes

1

answer

24

views

Is there such a notion as “effectively computable reductions” or would this be not useful

complexity-theory computability np polynomial-time-reductions theory

answered 4 hours ago 6005 1,141

0

votes

0

answers

18

views

Complexity of recursive algorithm

complexity-theory

asked 5 hours ago Karol Dowbecki 101

0

votes

0

answers

36

views

Show that for every language A, there exists a language B such that not B ≤m A

complexity-theory turing-machines

modified 9 hours ago John 1

1

vote

1

answer

18

views

Clarifiaction on the NP-hardness of k-SUM-variants

complexity-theory np

answered 11 hours ago narek Bojikian 3,563

1

vote

0

answers

14

views

One-way-function based on Friedberg numberings

complexity-theory formal-languages one-way-functions

asked 11 hours ago Harald Thomson 111

2

votes

1

answer

30

views

Composition of functions computable in logspace

complexity-theory turing-machines space-complexity

answered 12 hours ago Yuval Filmus 217k

-1

votes

0

answers

26

views

How is 0-1 knapsack problem a Class NP problem?

complexity-theory data-structures

asked 18 hours ago Dipendra Pant 1

0

votes

2

answers

62

views

Finding a Hamilton path in a Complete Euclidean Graph is in P

complexity-theory graphs np-hard

answered yesterday Ibai 125

4

votes

1

answer

163

views

Understanding details of NP-Hard definition

complexity-theory time-complexity np-complete np-hard

modified 2 days ago Izar Urdin 101

-1

votes

1

answer

81

views

Showing on-line P = NP

complexity-theory computability proof-techniques p-vs-np

modified 2 days ago dingalapadum 221

4

votes

1

answer

170

views

Maximum matching in a bipartite graph

complexity-theory graphs bipartite-matching bipartite-graph

modified 2 days ago Antti Röyskö 811

3

votes

3

answers

2k

views

What will happen to NP-Hard problems if P=NP

complexity-theory np-complete np-hard np

modified 2 days ago Ixer 73

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled