Skip to content

On Halting Problem and P ?= NP

March 21, 2013

Just some questions:

Does the halting problem <=> P = NP or P != NP? If not, what is the relation between the two problems? Does it exist?
Is there a class (set) of problems equivalent to the halting problem? –yes
What is the cardinality of this set?

If the cardinality of this set is uncountably (or even countably) infinite what does it mean for the implication arrow above? If it is uncountably infinite (moreover, if it is isomorphic to Aleph_alpha) does it follow the 2^n halting problem (the problem of halting an exponential number of turing machines) is of order 2^(Aleph_alpha)?

Allow m to be the cardinality of the set P and n to be the cardinality of the set NP. The halting problem is a subset of NP (classification grouping: MAX-3SAT problem).

Assume m < n or n > m. If we replace the value m with 2^m or n with 2^n (the problem of finding the solution to the power set of the problems in m/n) and m = n then we have constructed a problem such that m < n and/or n < m depending on one’s frame of reference.

Discuss?

-harbinger of night

Advertisements

From → Uncategorized

One Comment

Trackbacks & Pingbacks

  1. On Halting Problem and P ?= NP | paroleface

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: