P vs NP

INTRODUCTION

NP vs P is highly theoretical topic with vast practical applications.
Lets see in short what does it mean informally:

• P class problems:  That can be solved in polynomial time. That is their upper bound is O(n^k), where k is some positive integer. Now, it doesn't matter how large k is : even if it 1000, we still call O(n^1000) as P class problem.
  
• NP class problems: Any problem that is not solvable in polynomial time, but can be "verified" in polynomial time is NP problem. What the heck does that mean? It simple means that there exists no algorithm to solve the problem within polynomial limits. It may be solved in 2^n time or n! time; however once we get the solution, we can check whether it is correct in polynomial time.
  For example, lets take an example of Hamiltonian Path Problem In this problem, we need to find a path in the graph such that it reaches every vertex only once, except the source vertex which is also a destination vertex. Till date, there is no proven polynomial time algorithm for same. However once the path is found, we can easily check in polynomial time, that whether such path really exists and satisfies the problem criteria.
  Note 1: When we see "not solvable in polynomial", we mean that no such algorithm has been yet discovered. It is always possible that in future some one discovers (or at least proves that there exists) a polynomial algorithm.
  Note 2: Since every problem in P class can be verified in polynomial time (do we really need to verify, we can solve it :P ), we can conclude that P is a subset of NP.
  
• NPC Class Problem: Informally, it means those problems which are "hardest" or at least no easier than any problem in NP class. We will get to technical definitions later, but it simply means that if any problem in NPC can be solved in polynomial time, all the problems in NP class will have polynomial time. 

Motivation

Before proceeding further, one may say, why the heck we need to study this section. How does it matter if the problem is n^1000 or 2^n, they both are practically impossible to implement for any sufficiently large value of n,  and so why bother to study them in separate sections? 

So, here are some of reasons why we should study P vs NP problems:

1. If a polynomial time algorithm is discovered for any problem, there is always chance that we can reduce its complexity further in polynomial time. O(n^1000) maybe with some improvements could work in O(n^100) or even smaller.
2. On other hand, if a problem is proved to be NP; it is always better to solve it be approximation algorithms or find algorithms for specific instances of problem, rather than trying to find a general solution which would work fast.
3. Polynomial problems also possess closure properties. Which in simple terms means that you add,  multiply, combine more than one polynomial algorithm, and you would still obtain polynomial solution. We cannot make such a claim about NP problems. 
4. Another thing that Polynomial problem has is that it tends to retain polynomial time on different kinds of computation model, such as Abstract Turing Machine; or Random Access computational model.
5. Although it is widely believed that no polynomial solution exists for any NPC problem, proving that such a solution exists will lead to polynomial solutions for EVERY NP problem. On the other hand, no one has been able to prove that such a solution should exist (or not!). This is indeed the most popular open question in Computer Science. (In case anyone is interested, there is $1,000,000 prize associated with it - to anyone who can prove whether a polynomial solution can exist for NPC problem or not)

Now lets move to technical bits:

DECISION vs OPTIMIZATION

Throughout, Algorithms study, we came across several Optimization problems, where our goal is to find an optimal solution to a given problem. For example, finding shortest distance between two nodes in a graph; or Longest Common Sub-sequence for two strings and so on...

However, in world of NP, we will deal with Decision problems. Our goal is not to find an optimal solution, but rather finding that "such solution exists." 

First, let us learn how to convert any optimization problem in decision problem. For shortest distance problem, 

Optimization: In a graph G(V, E), find the shortest path between nodes S and D.

Decision: In a graph G(V, E), does there exist a path between S and D which is of maximum weight W?

Easy!

Now, why we use decisions rather than optimizations? Well, because they are easy to answer! It is always easier to answer "yes" or "no" rather than find an optimal solution to a problem.

Also, remember we are now trying to prove "lower bounds" for problem, rather than "upper bound" : and so if we can prove that a decision problem is hard, we can conclude that Optimization problem is hard. 

So, in short our job is easier. If we can prove that a decision problem is hard, it automatically follows that corresponding optimization would be hard. On the other hand, if optimization is easy, decision problem is easier.

REDUCTIONS

This is fairly easy. Let's say, we have two decision problems: A and B. We have already solved A, and now we would like to solve B.

Now, there exists a BLACK BOX. What it does, it takes instance of problem B (which we would like to solve) and *magically* convert it into instance  of problem A (which we have solved). 

This Black Box has following properties:

• It is polynomial time conversion.
• Its conversion is "true" i.e. whatever is the answer of output ("yes" or "no" - keep in mind it is decision problem) is the answer of input.

So, this is a way, we show most problems are NPC, we take one problem which we already had proved to be "NPC", and then use some conversion algorithm and conclude whether next problem is NPC or not.

*****

This is in short: highly non-technical, very low level introduction to P vs NP problems. 

Further introductory studies might include:

1. Deterministic vs Non-Deterministic models
2. Examples of NPC Problems : Clique, vertex cover, 3-CNF, Hamiltonian Path, Subset Problem etc.

Source: CLSR

Calculating Emotions

As we move to Robotics stage, as well as world which is increasingly becoming digital, it may be a topic of interest to be able to calculate intensity of emotion. This is in fact, a challenging task, since we haven't yet developed accurate algorithm which can always correctly predict what type of emotion would be generated for a given set of circumstances, leave alone how much of that emotion would be predicted.
One particular difficulty in the task is that no human respond with single emotion to any stimuli. A sentient response always consist of a group of emotions, with different intensities associated with them.

In this blog, I will try to work on relation between set of circumstances, and given emotion.

Before moving forward, let me review key terms :

• Emotion :  A state of feeling, or a state of mind derived from present circumstances and resulting in behavioral changes. Examples include : Anger, love etc.
• Intensity (of emotion) : How strong a feeling may be present. e.g. anger in high intensity can lead to rage, while high sexual desire can be termed as lust.
• Stimuli: In simple, words they are external circumstances to which a response must be given.

Our next job should be to investigate the factors on which intensity of emotion depends:

Other Emotions
Any emotion is dependent on other emotions. The level of anger clearly does depend on level of disgust which is felt; jealousy intensity depends upon both the love intensity as well as hatred intensity. (You intensity of jealousy does depend on how much you love your partner/how much you hate with whoever your partner is having an affair. Of course, intensity of jealousy will be dependent on other factors such as pride, trust etc also)

Thus, we get :

1. Intensity of emotion depends on intensities of other emotions.

A basic equation is then :

I_E = I_E1 +  I_E2 + ...

Trivially, next point should be that any intensity may add or may diminish the intensity of given emotion.

2. An Intensity may be positive, negative or zero.

• Emotions contributing positively are constructive, those with negative intensity are destructive, while one with zeroes (or near-about values) are indifferent for that emotion.

Now,

I_E = ∑ I_Ei 

Our range of i depends on us, and our data-base. In my opinion, we have three ways to achieve this equation, for every emotion, map out certain constructive and destructive emotions and iterate over them; second way is to iterate over every emotion in database, and thus calculate intensity; while third yet is to constrict ourselves to set of only few basic emotions and calculate with respect to them.
[A supplement, if needed, can be written describing advantages/disadvantages of each method]

• Basic Emotions: It is argued that with help of only few emotions, any emotion could be constructed, While No universal agreement is there on which emotions consist of basic emotions (or of there are basic emotions), one set as proposed by Plutchick is { joy,sadness ; acceptance, disgust; anger, fear; surprise, anticipation }

However,  we aren't quite done yet.

Each emotion affects other emotion by different degree. Surely, impact of surprise is less than impact of care if we are talking about emotion of love. It may be so, a stimuli generates lots of surprise in you, but the high value of surprise should not affect the intensity of love. 

This means each emotion is perceived by any emotion differently. Therefore, this perception or closeness  of any emotion to other emotion must be factored in our equation.

The most logical way to do that would be to multiply degree of closeness to that respective emotion.

I_E = ∑ I_Ei*D_Ei

There are various ways in which again degree can be implemented. One way to do so, would be to assign absolute degree as 1. If a degree is one, it means that particular emotion is certain to impact the emotion under consideration. Further, a degree could be implemented linearly or exponentially, as indicated by further research. (Linearly: a degree 0.6 emotion means that this equation is twice more impact-ful than 0.3 degree emotion on given emotion; while in exponential implementation, this may not be the case)

****************

This completes today's entry. In coming parts, we would view other factors affecting any emotion such as type of person who is responding to stimuli (under same set of circumstances, two persons react differently), type of relationship you share towards stimuli entities ( A same person may react differently to different person) and other things.