Interesting. It would have been better if we could...

2010-02-19T21:37:05.504-08:00

Interesting. It would have been better if we could identity life problems we encounter whether it is a problem in P, NP, is it NP-hard or NP-complete, or a problem that is BQP or BPP?

By what is commented recently, is it a preposition that we are a living algorithm? A living Turing machine?

I got here googling 'life is NP-hard', hop...

2009-10-21T07:22:41.198-07:00

I got here googling 'life is NP-hard', hoping someone's made a T-shirt of it. :) But your argument isn't quite foolproof of course, and I'm thinking a stronger one could be made.

First off, yes, you mixed NP-complete and NP-hard, but your proof would have come out easier if you hadn't. NP-Hard problems are any which are as hard as or harder than an NP problem. So life is NP-Hard as long as it contains any NP-Complete problems as a subset. The very fact that NP-Complete problems exist and some people want to solve them trivially makes life NP-Hard (for those people).

Now, a more interesting proof stems from understanding that there are thousands of problems which are NP-complete, and some of them are just idealized versions of everyday activities. Whenever we try to pack a box efficiently we are making an approximate solution to an NP-complete problem. When we try to plan an efficient route to our various destinations we are of course solving a mini tsp, which I'd say is a good metaphor for what everyone tries to do every day-plan an efficient route through the goals of the day.

Interestingly, NP problems are usually studied as decision problems, which in effect ask 'is it possible? If so how?' so any time we ask ourselves that question, and the answer can be checked for sanity in polynomial (usually linear or something akin to nlogn) time, we are doing something NP-hard.

To prove life NP-hard, of course, it would definitely have to be stated as a formal problem, meaning an input-output situation, which I'd say life isn't really as a whole. Furthermore to be NP-hard something has to be verifiable in P, and though significant subsets of life are, I doubt we can really check whether a life was well-lived in polynomial time. A life is like a program unleashed upon the world, and a life well-lived never halts. We can never know sometimes whether a program will halt; the halting problem is not verifiable in P or in exponential time or in any finite function of input size.

I guess I'll email you, assuming you were serious.

NP means Non-deterministic Polynomial-time

2009-07-25T23:55:33.270-07:00

NP means Non-deterministic Polynomial-time

I like your post, specially the title :-) Thanks f...

2009-06-01T16:16:37.167-07:00

I like your post, specially the title :-) Thanks for sharing.

Btw Anupam, NP means Not Polynomial.

Cheers,

Carl.

Lucid and enlightening. But what exactly do n and ...

2008-06-16T10:56:00.000-07:00

Lucid and enlightening. But what exactly do n and p stand for? the variables?

Comments on Gregable.: Life is NP-Hard

Interesting. It would have been better if we could...

I got here googling 'life is NP-hard', hop...

NP means Non-deterministic Polynomial-time

I like your post, specially the title :-) Thanks f...

Lucid and enlightening. But what exactly do n and ...