# The "cardinality of extended solution set" criterion for establishing the intractability of NP problems

@article{Arun2020TheO, title={The "cardinality of extended solution set" criterion for establishing the intractability of NP problems}, author={U. Arun}, journal={ArXiv}, year={2020}, volume={abs/2004.01491} }

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… Expand

#### Topics from this paper

#### One Citation

Technical Report Column

- Computer Science
- SIGACT News
- 2020

This report presents a meta-modelling system that automates the very labor-intensive and therefore time-heavy and therefore expensive and expensive process of manually cataloging and cataloging all the components of a smart phone. Expand

#### References

SHOWING 1-10 OF 14 REFERENCES

Computability and analysis: the legacy of Alan Turing

- Computer Science, Mathematics
- Turing's Legacy
- 2014

The theory of probability, which was born in an exchange of letters between Blaise Pascal and Pierre de Fermat in 1654 and developed further by Christian Huygens and Jakob Bernoulli, provided methods for calculating odds related to games of chance. Expand

A Simple Introduction to Computable Analysis

- 2009

1 1 Introduction During the last 60 years an extensive theory of computability and computational complexity has been developed (see e.g. Rogers Rog 67], Odifreddi Odi 89], Weih-rauch h W ei 87],… Expand

Gödel for Goldilocks: A Rigorous, Streamlined Proof of (a variant of) Gödel's First Incompleteness Theorem

- Mathematics, Computer Science
- 2014

In this exposition, G\"odel's first incompleteness theorem can be rigorously proved by a simpler middle approach, avoiding philosophical discussions and hand-waiving at one extreme; and also avoiding the heavy machinery of traditional mathematical logic, and many of the harder detail's of the original proof, at the other extreme. Expand

Some optimal inapproximability results

- Computer Science, Mathematics
- JACM
- 2001

We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations… Expand

A Functional Approach to Computability on Real Numbers

- Mathematics
- 2005

The aim of this thesis is to contribute to close the gap existing between the theory of computable analysis and actual computation. In order to study computability over real numbers we use several… Expand

A universal statistical test for random bit generators

- Mathematics, Computer Science
- Journal of Cryptology
- 2004

A new statistical test for random bit generators is presented which can detect any significant deviation of a device's output statistics from the statistics of a truly random bit source when the device can be modeled as an ergodic stationary source with finite memory but arbitrary (unknown) state transition probabilities. Expand

On the power of unique 2-prover 1-round games

- Computer Science
- Proceedings 17th IEEE Annual Conference on Computational Complexity
- 2002

A conjecture regarding the power of unique 2-prover games is made, which is called the Unique Games Conjecture, that is, the maximum acceptance probability of the verifier over all the prover strategies. Expand

On Computable Numbers, with an Application to the Entscheidungsproblem

- Mathematics
- 1937

1. Computing machines. 2. Definitions. Automatic machines. Computing machines. Circle and circle-free numbers. Computable sequences and numbers. 3. Examples of computing machines. 4. Abbreviated… Expand

An example of a computable absolutely normal number

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2002

This note gives a recursive reformulation of Sierpinski's construction which produces a computable absolutely normal number. Expand

The Kolmogorov-Smirnov Test for Goodness of Fit

- Mathematics
- 1951

Abstract The test is based on the maximum difference between an empirical and a hypothetical cumulative distribution. Percentage points are tabled, and a lower bound to the power function is charted.… Expand