So the definition of P can be given as a statement that is reduced in such a way that still contains enough information to derive a solution for it? It strangely resembles to me that a language for information description that can store all information within any constructible sentence could only be used to formulate P problems. Like reversible computation, where you always know a previous step when given any input. It gives me a bizarre feeling of amusement if all I just said makes sense at all :)
P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed. I show a solution to that problem as follows: Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP. You could read the details in the link below… hal.archives-ouvertes.fr/hal-01509423/document
It's always so illuminating and not-boring to hear Avi's talks...
So the definition of P can be given as a statement that is reduced in such a way that still contains enough information to derive a solution for it? It strangely resembles to me that a language for information description that can store all information within any constructible sentence could only be used to formulate P problems. Like reversible computation, where you always know a previous step when given any input. It gives me a bizarre feeling of amusement if all I just said makes sense at all :)
At 20:00, the product should equal 147,573,952,589,676,412,927 with 9 not 8 in the billions place.
Beautiful.!
P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed.
I show a solution to that problem as follows:
Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.
You could read the details in the link below…
hal.archives-ouvertes.fr/hal-01509423/document
the problem's solution has big effect on human's knowledge and sense of world
Your “proof” of several of your “Lemmas” contain clear non sequiturs.