Jump to content

Frank Vega Delgado

Members
  • Content Count

    6
  • Joined

  • Last visited

Community Reputation

3 Neutral

About Frank Vega Delgado

  • Rank
    Lepton

Profile Information

  • Favorite Area of Science
    Computer Science
  1. fiveworlds, I have lost the connection between your arguments and the idea of the paper... However, thanks for your comment...
  2. You can follow the paper in the following link: https://hal.archives-ouvertes.fr/hal-01509423
  3. Stranger, when I wrote the paper I thought zero as a positive (non-negative) integer. Indeed, I did not mention in the paper that the zero represents the empty set. The definition of zero as a positive (non-negative) integer really depends on context, so in our case we could take it as a valid argument without problem. At the same time, I did not discuss in the paper how I would represent the empty set. Indeed, I could formally represent it as a symbol which is not in the binary alphabet (just to put you an example) and later we could encoded as a specific binary string if we want... Stranger, thank you so much for your comment... fivewords, it follows from the self definition that a set S with n positive integers is represented by a Boolean circuit C, if and only if when a bit integer j is not in S, then C will not accept j (as result of using the Boolean logic over the definition). Hence, the empty set must be represented necessarily by the Boolean circuits which do not accept any input. Certainly, if some circuit C accepts some binary input x, then C will represent some set S which contains at least the bit integer x as element. fivewords, thank you very much for your comment...
  4. I think you cut the sentence by mistake, because the whole sentence in the paper says "Proof: Since the empty set cannot be represented by a Boolean circuit C such that there is some truth assignment T, appropriate to C, where T( C ) = true, then ...". Of course, the empty set can actually be represented by a Boolean circuit. However, it cannot be represented by a Boolean circuit which accepts at least some input if we use the definition which appears in the paper and that is exactly the other fragment of the sentence that you missed (the fragment after ".. such that..."). I will share the definition so you could understand... Definition: 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 j if and only if j is in S. fivewords, thank you very much for your comment...
  5. DrKrettin and Raider5678, thanks for your comments!!! Raider5678, if you have any doubt about the paper do not hesitate to ask me!!! DrKettin, I think to claim the million dollar prize, the paper need to be published in a journal and be accepted by the scientific community within two years.
  6. 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 pdf attachment below onpversusnp.pdf
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.