Linked Questions

104 votes
5 answers
17k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction....
user avatar
  • 70.8k
52 votes
6 answers
14k views

Why are some games np-complete?

I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? ...
user avatar
  • 637
46 votes
3 answers
88k views

What exactly is polynomial time?

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
user avatar
  • 563
40 votes
3 answers
5k views

Decision problems vs "real" problems that aren't yes-or-no

I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
user avatar
  • 20.3k
30 votes
5 answers
11k views

"NP-complete" optimization problems

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
user avatar
26 votes
5 answers
16k views

What is meant by "solvable by non deterministic algorithm in polynomial time" [duplicate]

In many textbooks NP problems are defined as: Set of all decision problems solvable by non deterministic algorithms in polynomial time I couldn't understand the part "solvable by non deterministic ...
user avatar
  • 2,111
23 votes
3 answers
2k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
user avatar
  • 505
16 votes
3 answers
808 views

Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
user avatar
  • 1,085
14 votes
5 answers
7k views

Flaw in my NP = CoNP Proof?

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out? Let A be some problem in NP, and let M be the ...
user avatar
  • 171
14 votes
1 answer
306 views

How can you bound the error of an approximation without knowing the optimal solution?

I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length ...
user avatar
13 votes
3 answers
5k views

P, NP and specialised Turing Machines

I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the ...
user avatar
  • 291
10 votes
2 answers
6k views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...
user avatar
10 votes
2 answers
374 views

Combinatory interpretation of lambda calculus

According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says: The combinatory interpretation of the lambda calculus is known to be imperfect, because it does ...
user avatar
  • 519
10 votes
2 answers
2k views

Simple graph canonization algorithm

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
user avatar
  • 1,475
8 votes
1 answer
566 views

Relaxed Bin Packing Problem

The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin. Is there an ...
user avatar
  • 201

15 30 50 per page
1
2 3 4 5
9