Skip to main content

P vs NP Behavior

Today, our police squad went to a mountain in Seoul, looking for an elderly man who was suspected of attempting suicide. (After 6.5 hours of searching, we were ordered to end the search. As of the time of this writing, the man has not yet been found.)

Because I drive our squad's bus, I had the privilege to wait inside the bus. This was in case someone tried to break in, or in case someone needed me to relocate the bus. I parked the bus on the side of the road, just below the hiking trail.

During the long wait, hikers passed by left and right. I noticed that the hikers coming from the left would pause, look, and (if they had companions) mention the existence of the police bus before moving on. Meanwhile, hikers from the right rarely paused.
Pause vs No Pause
I believe that this behavior could be explained by an amount of time that is needed to appreciate an unexpected sight. I will call this duration surprise time. Highly unusual and intriguing moments have long surprise times. When a large meteor falls from the sky, it could be expected that almost everyone would pull out their phones and stare for a good 10 minutes.

Less intriguing, and somewhat unusual events—such as a police bus in the mountain—could also catch people by a smaller surprise, causing them to stare for a few seconds before moving on. This is what happened with the hikers who came from the left. The ones that came from the right had already seen the bus for the entire duration of the surprise time of a few seconds by the time they passed, thus the need to linger around the bus was eliminated. (The paint diagram above shows that the steep angle on the left side of the bus prevented the left side hikers from seeing the bus until they passed.)

Because science values quantities, the science of psychology could perhaps apply surprise time in the other direction. That is, instead of saying that more surprising events have longer surprise times, they could assume that longer surprise times imply higher unusual-ness. Using surprise time, they could measure just how weird some unusual events are.

Comments

  1. Frank VegaApril 26, 2017 at 3:04 AM

    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:

    http://vixra.org/pdf/1704.0335v1.pdf

    ReplyDelete
  2. Frank VegaApril 28, 2017 at 12:52 AM

    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...

    https://hal.archives-ouvertes.fr/hal-01509423/document

    ReplyDelete
  3. Hajong LeeMay 13, 2017 at 11:23 AM

    꿀빨면서 이런 생각하는구나... <3

    ReplyDelete
  4. Hajong LeeMay 13, 2017 at 11:34 AM

    But did you write P vs. NP because of Pause vs. No Pause and also thought of the mathematics computational P vs. NP question? Hahaha...

    ReplyDelete

Post a Comment

Popular posts from this blog

A Question on Reincarnation

Does reincarnation maintain the number of organisms living in the world? Suppose there is a world where there are only three living organisms, and they are reincarnated when they die. What happens when one is about to die? If the remaining two reproduce sexually, will they forced to procreate as the third one dies, thereby maintaining the number of organisms in that world? What if two individuals die at once? Would single celled organisms naturally evolve out of protein? Perhaps the number of living organisms and souls is not strictly maintained. This would explain the exponential growth and decay of populations. But if everything is reincarnated, how would this be possible? Where would new life come from?
7 comments
Read more

Deromanticizing Numbers

My first post (other than the introduction ):  A discussion on the obsession with seemingly relevant, yet probably meaningless numbers (like "first"). Should We Stop Celebrating New Years? Over the last few years, I tried not to take notice of New Years. I thought it was silly of us to celebrate the fact that a 4 digit integer reached its successor. I am not saying that rather than celebrating, we should instead despair the fact that we are a year closer to our deaths (though this is true). Nor am I trying to stop anyone else from celebrating. I am simply perplexed about the fact that we celebrate an event that is, upon reflection, quite ordinary. Celebration of a new year every year suggests that there is not that much to celebrate in life and too much need for celebration. This idea can be applied on other cultural phenomena, especially anything annual, like birthdays and anniversaries, but these examples are redundant. Other non-annual applications of this idea incl...
4 comments
Read more

Behind the Facade of High SAT Scores

Most people do not care much about scores after high school, and even if the topic comes up, I have found that many top scorers (understandably) have a tendency to refrain from speaking too much on it. This is not helpful for younger students who need genuine advice. Here is my experience . My real experience, not a you can do it too  success story. When I started, I had no idea where to start. I was a sophomore in high school, and all my Asian friends were studying for the SAT in hagwons . I had never been to a hagwon . The y told me these hagwons provide information on everything about the test, such as when and where to take it, the best times to take it, the best times to prepare for it, and most importantly, how to prepare for it. Very little effort was needed to convince my parents that I wanted to enroll for the summer. Come summer vacation. I took five weeks of classes in June and July, Monday to Friday, from 7 a.m. to noon. Basically it was around 2 hours of Read...
3 comments
Read more