## np-complete

### Find the best combination from a given set of multiple sets

Say you have a shipment. It needs to go from point A to point B, point B to point C and finally point C to point D. You need it to get there in five days for the least amount of money possible. There are three possible shippers for each leg, each with their own different time and cost for each leg: Array ( [leg0] => Array ( ...

### Algorithm to find which numbers from a list of size n sum to another number

I have a decimal number (let's call it goal) and an array of other decimal numbers (let's call the array elements) and I need to find all the combinations of numbers from elements which sum to goal. I have a preference for a solution in C# (.Net 2.0) but may the best algorithm win irrespective. Your method signature might look somethin...

### Polynomial time algorithm for finding a Hamiltonian walk in a graph

Is there a polynomial time algorithm for finding a Hamiltonian walk in a graph? My algorithm is N factorial and is really slow. ...

### What's "P=NP?", and why is it such a famous question?

The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting? Oh, and for extra credit, please post a proof of the statement's truth or falsehood. :) ...

### What is a good algorithm for compacting records in a blocked file?

Suppose you have a large file made up of a bunch of fixed size blocks. Each of these blocks contains some number of variable sized records. Each record must fit completely within a single block and then such records by definition are never larger than a full block. Over time, records are added to and deleted from these blocks as records ...

### How can I programmatically determine how to fit smaller boxes into a larger package?

Does anyone know of existing software or algorithms to calculate a package size for shipping multiple items? I have a bunch of items in our inventory database with length, width and height dimesions defined. Given these dimensions I need to calculate how many of the purchased items will fit into predefined box sizes. ...

### Solving the NP-complete problem in XKCD

The problem/comic in question: http://xkcd.com/287/ I'm not sure this is the best way to do it, but here's what I've come up with so far. I'm using CFML, but it should be readable by anyone. <cffunction name="testCombo" returntype="boolean"> <cfargument name="currentCombo" type="string" required="true" /> <cfargument name="cu...

### What is an NP-complete problem?

What is an NP-complete problem? Why is it such an important topic in computer science? ...

### how were the first NP-complete problems shown to be NP-complete?

From the wikipedia entry on NP-Complete: "The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it" I'm pretty sure that I understand this: If I have a problem, I can show that it is NP-Complete if I: show that it is in NP (a solution t...

### Subset summing

I have a problem related to the subset sum problem and am wondering if the differences make it easier, i.e. solvable in a reasonable amount of time. Given a value V, a set size L, and a sequence of numbers [1,N] S, how many size L subsets of S sum to less than V? This is different than the subset sum problem in three ways: I care h...

### Non-exponential solution to maze problem?

Given a n*n-sized multi-headed acyclic graph where each node has at most three children and three parents, is there an non-exponential algorithm to identify whether a n-length path exists where no two nodes share the same value, and every value of a set is accounted for? Basically, I have an n*n maze where each space has a random value ...

### NP-Complete reduction (in theory)

I want to embed 3 NP-Complete problems(2 of them are known to be NP-Complete, 1 of them is my own idea). I saw "this question" and got idea about reinterpreting embedding problems in theory: The Waiter is The Thief. Tables are store. Foods are valued items which has different weight. Thief know all the items' price and weight before th...

### Is minimization of boolean expressions NP-Complete?

I know that boolean satisfiability is NP-Complete, but is the minimization/simplification of a boolean expression, by which I mean taking a given expression in symbolic form and producing an equivalent but simplified expression in symbolic form, NP-Complete? I'm not sure that there's a reduction from satisfiability to minimization, but I...

### Have you ever had a business requirement that turned out to be an NP-Complete problem?

NP-completeness seems to me like one of those things that's mostly just theoretical and not really something you'd run into in a normal work environment. So I'm kind of curious if anyone's ever run into a problem at their job that turned out to be NP-complete, and that the design needed to be changed to accommodate for it? ...

### Algorithm to Divide a list of numbers into 2 equal sum lists

There is a list of numbers. The list is to be divided into 2 equal sized lists, with a minimal difference in sum. The sums have to be printed. #Example: >>>que = [2,3,10,5,8,9,7,3,5,2] >>>make_teams(que) 27 27 Is there an error in the following code algorithm for some case? How do I optimize and/or pythonize this? def make_teams(q...

### Possible NP-complete problem?

I'd just like someone to verify whether the following problem is NP-complete or if there is actually a better/easier solution to it than simple brute-force combination checking. We have a sort-of resource allocation problem in our software, and I'll explain it with an example. Let's say we need 4 people to be at work during the day-shi...

### Is this "Valid mathematical expression" problem P, or NP?

This question is purely out of curiosity. I am off school for the summer, and was going to implement an algorithm to solve this just for fun. That led to the above question, how hard is this problem? The problem: you are given a list of positive integers, a set of mathematical operators and the equal sign(=). can you create a valid math...

### What is the difference between a 'combinatorial algorithm' and a 'linear algorithm'?

Or rather, what is the definition of a combinatorial algorithm and a linear algorithm, resp.? To make it clear because obviously the first responders misunderstood the question: I am not looking for a definition of an algorithm running in linear time vs non-linear time. A linear algorithm is somehow related to linear programming, which ...

### How to design acceptance probability function for simulated annealing with multiple distinct costs?

I am using simulated annealing to solve an NP-complete resource scheduling problem. For each candidate ordering of the tasks I compute several different costs (or energy values). Some examples are (though the specifics are probably irrelevant to the question): global_finish_time: The total number of days that the schedule spans. split_...

### How to find what numbers in a set add up to another given number?

Here's a problem that I seem to be running into working with an accounting system. I have a set of transactions, but their sum does not equal the amount that the accounting department thinks that it should. They are not questioning the math, just the transactions being included :p Is there an algorithm that would help me determine whic...