If an algorithm A always works in polynomial time, it speaks for P=NP, therefore, it is expressed in my paper as "special case of P=NP".
Upvote
0
-
Starting today August 7th, 2024, in order to post in the Married Couples, Courting Couples, or Singles forums, you will not be allowed to post if you have your Marital status designated as private. Announcements will be made in the respective forums as well but please note that if yours is currently listed as Private, you will need to submit a ticket in the Support Area to have yours changed.
-
CF has always been a site that welcomes people from different backgrounds and beliefs to participate in discussion and even debate. That is the nature of its ministry. In view of recent events emotions are running very high. We need to remind people of some basic principles in debating on this site. We need to be civil when we express differences in opinion. No personal attacks. Avoid you, your statements. Don't characterize an entire political party with comparisons to Fascism or Communism or other extreme movements that committed atrocities. CF is not the place for broad brush or blanket statements about groups and political parties. Put the broad brushes and blankets away when you come to CF, better yet, put them in the incinerator. Debate had no place for them. We need to remember that people that commit acts of violence represent themselves or a small extreme faction.
-
We hope the site problems here are now solved, however,
if you still have any issues, please start a ticket in Contact Us
Proof of mathematical classes P=NP using Religion
- Thread starter Omega constant
- Start date
Hans Blaster
Area Meathead
- Mar 11, 2017
- 23,908
- 17,653
- 56
- Country
- United States
- Gender
- Male
- Faith
- Atheist
- Marital Status
- Private
- Politics
- US-Democrat
And you posted about something from a well known crank? Sure dude, sure. If ya are why did you write nonsense like "dark energy might be a spirit"
(I haven't seen Martila around lately. So much for that fool.)
Upvote
0
PloverWing
Episcopalian
- May 5, 2012
- 5,551
- 6,621
- Country
- United States
- Gender
- Female
- Faith
- Anglican
- Marital Status
- Married
Lots of algorithms work in polynomial time, so just producing one more polynomial-time algorithm for some problem doesn't help. The P=NP problem is showing that these two classes:
P = the class of languages that are accepted in polynomially bounded time by a deterministic Turing Machine
NP = the class of languages that are accepted in polynomially bounded time by a nondeterministic Turing Machine
are the same class. Clearly, any language in P is also in NP. The hard part (currently unsolved) is showing that every language in NP is also in P.
Restating it a little less formally, we could define the classes this way:
P = the set of problems that can be solved by a deterministic algorithm in polynomial time
NP = the set of problems that can be solved by a nondeterministic algorithm in polynomial time
Proving that P=NP means proving that all problems that can be solved in polynomial time by a nondeterministic algorithm could also be solved by a deterministic algorithm in polynomial time. It's not enough to show that some algorithms have a polynomial runtime; that part is obvious. The proof needs to address the problems for which (currently) only efficient nondeterministic algorithms are known, and it needs to address ALL of these problems.
Upvote
0
If Miracle-All-knowing Jesus is there, will it be P=NP? All problems will be solving in zero time.
Upvote
0
PloverWing
Episcopalian
- May 5, 2012
- 5,551
- 6,621
- Country
- United States
- Gender
- Female
- Faith
- Anglican
- Marital Status
- Married
Presumably, God the Son knows the answer to all computational problems. But remember that when we're evaluating "polynomial time", we're counting Turing Machine steps: If the Turing Machine requires y steps to compute its answer for an input of length n, and we express y as a function of n, is that function a polynomial (like n squared) or a more rapidly-growing function? "God told me" is not one of the computational steps a Turing Machine can carry out, so it doesn't help us here.
If you want to be slightly less formal, think of counting the computational steps taken by a C program or a Java program. Again, "God told me" is not one of the operations provided in C or Java (though it would often be handy!
), so we have to stick with mundane operations like assignment and addition.tl;dr: The omniscience of God does not provide us with an answer to P=?NP.
Upvote
0
If All-knowing being is part of algorithm, all computations are being done in one step: a prayer to Him.
Upvote
0
PloverWing
Episcopalian
- May 5, 2012
- 5,551
- 6,621
- Country
- United States
- Gender
- Female
- Faith
- Anglican
- Marital Status
- Married
But an all-knowing being is not part of the algorithm, if we're talking about P and NP. In one computational step on a Turing Machine, the machine is allowed to look at the current state and current tape symbol; it then changes state, writes a new symbol on the tape, and moves the tape head. That's it. No divine revelations, no pocket calculators, even. Those are the computational steps we're counting when we measure the run-time of the algorithm.
It's something like saying that I could easily win a game of chess by reaching across the chessboard and picking up my opponent's king and putting it into my pocket. Yes, there's a sense in which I've captured my opponent's king, but I've done something that's not one of the legal moves in chess, so I haven't actually won the game.
Determining whether a problem is in P, or is in NP, is playing a game by a very strict set of rules. Divine revelation isn't one of the rules we get to use when we're working with Turing Machines.
Upvote
0
Similar threads
