Sure, I'll try and present my considerations or reason for asking this deep question. Since I lack the skills, I'll just start out by saying that since logic has been progressing in a manner where one does not know whether that logic or a system of logic is universal, then assuming that logical monism is true, then one can think that it should be possible to find a hermetic/tautological language.

But, to really reduce what I have to say or rephrase it as a question, are the implications of Gödel's Incompleteness Theorems somehow restricting us or preventing us from arriving at an answer? Is it that because of his theorems, scientists don't believe that P=NP? I'm only saying this because it is thought that for P=NP to be proven it would have to be a formally complete and consistent complexity class.

There are numerous Youtube videos on P v. N-P. Best are from MIT. That's the place to start. A quick test: do you, gentle reader, know what N-P stands for?

@tim wood & @Shawn
Being honest and lazy, no!
And a paragraph or two explaining the "implications of[ and what are] Godel's Incompleteness Theorems" may stimulate interest. For sure, there will be differences of understanding/opinion of those two 'bits' for starters.

personally interested but clueless smile

Seems easy to get lost in this, but doesn't this ultimate resolve to computational hardware? Like, sure my old Toyota can hit 90, maybe. I don't think it's a wise idea. Whereas my Dodge Charger, a newer model boasting newer engineering and thus performance, shouldn't break a sweat. I'm sure there's a complexity to it that myself and surely others are not familiar with, but, the question itself seems to be laid out in clearly understandable terms. It's 1's and 0's after all, information traversing circuits to the best speed said circuits (biological components) can support, so, I guess it falls onto what in theory would be the most "complex" problem, which to me invokes the idea of Pi. Which is infinite? Which makes it a conundrum by titular definition not really any actual unmet real-world challenge or of any actual beneficial utility. Kind of just a fun thought experiment really. That aside, anything short of that, that can be defined should be able to be reasonably enough determined how quickly it can be "checked for correctness" if whatever infrastructure of software capable of actually determining such. I'm sure there's a million and one things I'm not privy to here but, the simple question gets more complicated when the word "easy" seems to have two different meanings, one simply meaning "possible" (given enough time) and the other meaning convenient (in a short, humanly-acceptable amount of time).

While I'm sure there's many who can shed a greater light on this I question whether or not the philosophical aspect is of much depth. Little more than, "hey what happens when we can invent a car that can go from 0 to 60 in less time than it would take to break your neck if you were behind the wheel?" Again it's interesting to know in like a trivial tidbit sense sort of way but doesn't really seem to be of much actual application to any realistic problem people actually care to solve or would have any real benefit.

Again, any elucidation or clarification to the "point" of this dilemma (what solving it would offer as benefit) would be appreciated.

personally interested but clueless smile — kazan

Forget Godel in this context. He has nothing to do with it. The question of Pv.NP is about, basically, how long it takes a computer to solve a problem, and how much longer it takes as the problem has more inputs. "The travelling salesman" is a well-known example of the kind of problem considered. A salesman has to visit several cities: what is the best routing for him (quickest, shortest, cheapest, whatever)? If it's four cities, not too hard to figure out. If a lot of cities, then it takes a long time to figure it out. Time in this case meaning computer steps.

There is usually a formula that gives the number of steps as a function of the inputs. That is, as the number of inputs increases, the number of steps needed to solve the problem also increases. With n as the variable number of inputs, such a formula might look like this: f(n) = n^3 + n^2 - 15n +26. And this of course is just a polynomial function. As you can see, as n increases, the value of f(n) increases: the computer time increases. But because it's a polynomial, the rate of increase in most cases is felt to be manageable; it doesn't increase "too fast."

But for some problems the rate of increase in time needed as inputs increase is exponential, wa-ay too fast. Such a formula might look like this: g(n) = 4^n + 2^n + 21n+ 15. So, if the first is a polynomial time increase, this is an exponential increase, also called a non-polynomial increase. And other non-polynomial functions can increase even faster.

You might feel justified in thinking that Pv.NP stood for polynomial v. non-polynomial. But it does not. Instead it stands for polynomial (time) v. non-deterministic polynomial (time). And this introduces another wrinkle.

By assumption (not always true) while the solution to a problem might take months, years, decades or more to generate, verifying that it is the solution would be a very much quicker process (polynomial time). The idea is that you have a magic computer that guesses the right solution, or in other words does not operate deterministically, and given that solution, it can be verified in P time.

NP, then, stands for problems that at the moment seem to require an exponential or greater increase in time to solve (as the number of their inputs increases) but whose solutions can (presumably) be verified in P time. The question, then - and fame and fortune to him or her who answers - is if NP turns out to be the same as P, or if NP and P are different.

If NP is P, that will mean that someone has discovered an efficient way to solve a whole lot of difficult problems, mostly a good thing. It will mean, for example, that if your salesman has to visit one hundred cities, you could pretty quickly set his schedule at absolute maximum efficiency - which at the moment cannot be done. (Give it a try.)

Now watch a couple of Youtube videos on P v. NP.


.

@tim wood,
Thank you for your time and patience. So the current solution is to compress a number (as many as is "logical") of inputs into a single variable/step to save the number of steps, hence time etc. But, computing is still a one step at a time method/programme....Vaguely right?
And the search is for beyond the draconian sequencial limits of logic i.e. what Shawn calls "a formal and consistent complexity class" that is still "logical"? A bit like Quantum and Relativity needing not only a unifying theory but also not too sure about the Quantum bit yet.

just scratched the surface smile