Source author record

Craig Alan Feinstein

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.GM General Literature math-ph math.AP math.MP Other Computer Science

Catalog footprint

Research overview

10works

7topics

0close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Dialogue Concerning The Two Chief World Views

In 1632, Galileo Galilei wrote a book called \textit{Dialogue Concerning the Two Chief World Systems} which compared the new Copernican model of the universe with the old Ptolemaic model. His book took the form of a dialogue between three philosophers, Salviati, a proponent of the Copernican model, Simplicio, a proponent of the Ptolemaic model, and Sagredo, who was initially open-minded and neutral. In this paper, I am going to use Galileo's idea to present a dialogue between three modern philosophers, Mr. Spock, a proponent of the view that $\mathsf{P} \neq \mathsf{NP}$ , Professor Simpson, a proponent of the view that $\mathsf{P} = \mathsf{NP}$ , and Judge Wapner, who is initially open-minded and neutral.

preprint2014arXiv

Puzzle: Zermelo-Fraenkel set theory is inconsistent

In this note, we present a puzzle. We prove that Zermelo-Fraenkel set theory is inconsistent by proving, using Zermelo-Fraenkel set theory, the false statement that any algorithm that determines whether any $n \times n$ matrix over $\mathbb F_2$ , the finite field of order 2, is nonsingular must run in exponential time in the worst-case scenario. The object of the puzzle is to find the error in the proof.

preprint2014arXiv

Trapping Regions for the Navier-Stokes Equations

In 1999, J.C. Mattingly and Ya. G. Sinai used elementary methods to prove the existence and uniqueness of smooth solutions to the 2D Navier-Stokes equations with periodic boundary conditions. And they were almost successful in proving the existence and uniqueness of smooth solutions to the 3D Navier-Stokes equations using the same strategy. In this paper, we modify their technique to obtain a simpler proof of one of their results. We also argue that there is no logical reason why the 3D Navier-Stokes equations must always have solutions, even when the initial velocity vector field is smooth; if they do always have solutions, it is due to probability and not logic.

preprint2012arXiv

Complexity Science for Simpletons

In this article, we shall describe some of the most interesting topics in the subject of Complexity Science for a general audience. Anyone with a solid foundation in high school mathematics (with some calculus) and an elementary understanding of computer programming will be able to follow this article. First, we shall explain the significance of the P versus NP problem and solve it. Next, we shall describe two other famous mathematics problems, the Collatz 3n+1 Conjecture and the Riemann Hypothesis, and show how both Chaitin's incompleteness theorem and Wolfram's notion of "computational irreducibility" are important for understanding why no one has, as of yet, solved these two problems.

preprint2012arXiv

The Computational Complexity of the Traveling Salesman Problem

In this note, we show that the Traveling Salesman Problem cannot be solved in polynomial-time on a classical computer.

preprint2011arXiv

2-State 3-Symbol Universal Turing Machines Do Not Exist

In this brief note, we give a simple information-theoretic proof that 2-state 3-symbol universal Turing machines cannot possibly exist, unless one loosens the definition of "universal".

preprint2011arXiv

An Elegant Argument that P is not NP

In this note, we present an elegant argument that P is not NP by demonstrating that the Meet-in-the-Middle algorithm must have the fastest running-time of all deterministic and exact algorithms which solve the SUBSET-SUM problem on a classical computer.

preprint2011arXiv

Is it possible to compute the Moebius function without factoring?

It has been well known since Fermat's Little Theorem was first published that it is possible to determine that a number is composite without determining any of its nontrivial factors. It is natural to ask whether it is also possible to compute the Moebius function of a composite number without determining any of its nontrivial factors. In this note, we argue that this is impossible.

preprint2011arXiv

The Collatz 3n+1 Conjecture is Unprovable

In this paper, we show that any proof of the Collatz 3n+1 Conjecture must have an infinite number of lines; therefore, no formal proof is possible.

preprint2011arXiv

The Riemann Hypothesis is Unprovable

In this note, we give a simple proof that the Riemann Hypothesis is unprovable in any reasonable axiom system.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Craig Alan Feinstein

Research overview

Is this your work?

10 publications

Dialogue Concerning The Two Chief World Views

Puzzle: Zermelo-Fraenkel set theory is inconsistent

Trapping Regions for the Navier-Stokes Equations

Complexity Science for Simpletons

The Computational Complexity of the Traveling Salesman Problem

2-State 3-Symbol Universal Turing Machines Do Not Exist

An Elegant Argument that P is not NP

Is it possible to compute the Moebius function without factoring?

The Collatz 3n+1 Conjecture is Unprovable

The Riemann Hypothesis is Unprovable

See the researcher in context

Building this map preview