  The intractability of any problem and the randomness of its solutions have an
obvious intuitive connection. However, the challenge till now has been that
there is no practical way to firmly establish if the solution to a problem is
actually random (or whether it has some hidden undiscovered structure, which
upon being detected would render it non-random). This has prevented the
conclusive declaration of hard problems (such as NP) as being definitely
intractable. For dealing with this, a concept called "extensibility" of a
sequence is developed. Based on this, a criterion termed as "cardinality of
extended solution set" is conceived to ascertain the (non)randomness of any
sequence. Further, this can then be used to establish the (in)tractability of
any problem depending on whether its solutions are random or non-random. This
criterion is applied to problems such as 2-SAT, 3-SAT and hardness of
approximation to analyze their (in)tractability. Finally, a proof for the
validity of the Unique Games Conjecture based on the same criterion is also
presented.
