Hasil untuk "cs.CC"

Gregory D. Baker

$p$-adic linear regression is the problem of finding coefficients $β$ that minimise $\sum_i |y_i - x_i^\topβ|_p$. We prove that computing an optimal solution is NP-hard via a polynomial-time reduction from Max Cut using a regularisation gadget.

Jason Yang

We present a simple proof that finding a rank-$R$ canonical polyadic decomposition of a 3-dimensional tensor over a finite field $\mathbb{F}$ is fixed-parameter tractable with respect to $R$ and $\mathbb{F}$. We also show a nontrivial upper bound on the time complexity of this problem.

Neil Immerman

I was a student of Juris Hartmanis at Cornell in the late 1970's. He believed that there was great potential in studying restricted reductions. I describe here some of his influences on me and, in particular, how his insights concerning reductions helped me to prove that nondeterministic space is closed under complementation.

Saeed Asaeedi

A Neighborhood Balanced Coloring (NBC) of a graph is a red-blue coloring where each vertex has the same number of red and blue neighbors. This work proves that determining if a graph admits an NBC is NP-complete. We present a genetic algorithm to solve this problem, which we implemented and compared against exact and randomized algorithms.

Lev Gordeev, Edward Hermann Haeusler

In this paper we present a more transparent upgrade of our proofs and comment on Jerabek's paper [8] that tried to refute our results by providing exponential lower bounds on the implicational minimal logic.

Emil Jeřábek

We show that the sum of a sequence of integers can be computed in linear time on a Turing machine. In particular, the most obvious algorithm for this problem, which appears to require quadratic time due to carry propagation, actually runs in linear time by amortized analysis.

David Ponarovsky

We show that given two arbitrary states $\ketψ,\ketφ$ it is impossible to compute the transformation: $ \ketψ\ketφ \mapsto \ketψ\left( \mathbb{I} - 2 \ketψ\braψ \right)\ketφ $ The contradiction of the existence of such operator follows by showing that using it, two players can compute the disjoints of their sets in a single round and $O\left( \sqrt{n} \right)$ communication complexity, which shown by Braverman to be impossible \cite{Braverman}.

Samuel Epstein

We show that outliers occur almost surely in computable dynamics over infinite sequences. Ever greater outliers can be found as the number of visited states increases. We show the Independence Postulate explains how outliers are found in the physical world. We generalize the outliers theorem to uncomputable sampling methods.

Ali Çivril

We show that the problem of determining the feasibility of quadratic systems over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$ requires exponential time. This separates P and NP over these fields/rings in the BCSS model of computation.

Per Alexandersson

Some classical graph problems such as finding minimal spanning tree, shortest path or maximal flow can be done efficiently. We describe slight variations of such problems which are shown to be NP-complete. Our proofs use straightforward reduction from $3$-SAT.

Abdallah Saffidine, Sébastien Lê Cong, Sophie Pinchinat et al.

We introduce a new decision problem, called Packed Interval Covering (PIC) and show that it is NP-complete.

Alexei Miasnikov, Alexander Ushakov

In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.

Jonathan Weed

In this paper, we show that the problem of determining whether one player can force a win in a multiplayer version of the children's card game War is PSPACE-hard. The same reduction shows that a related problem, asking whether a player can survive k rounds, is PSPACE-complete when k is polynomial in the size of the input.

Mikhail Tikhomirov

A graph $G$ is embeddable in $\mathbb{R}^d$ if vertices of $G$ can be assigned with points of $\mathbb{R}^d$ in such a way that all pairs of adjacent vertices are at the distance 1. We show that verifying embeddability of a given graph in $\mathbb{R}^d$ is NP-hard in the case $d > 2$ for all reasonable notions of embeddability.

Nicolas Brener

The Turing machine (TM) and the Church thesis have formalized the concept of computable number, this allowed to display non-computable numbers. This paper defines the concept of number "approachable" by a TM and shows that some (if not all) known non-computable numbers are approachable by TMs. Then an example of a number not approachable by a TM is given.

Javaid Aslam

This paper provides a further refinement to the previous response by introducing new structures and algorithms for counting VMPs of common \emph{Edge Requirement} (ER) and hence for counting the perfect matchings.

Arno Pauly

We consider the computational complexity of the question whether a certain strategy can be removed from a game by means of iterated elimination of dominated strategies. In particular, we study the influence of different definitions of domination and of the number of different payoff values. In addition, the consequence of restriction to constant-sum games is shown.

Philippe Moser

In this paper we introduce a general framework for defining the depth of a sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions.

R. A. Cohen

The open question, P=NP?, was presented by Cook (1971). In this paper, a proof that P is not equal to NP is presented. In addition, it is shown that P is not equal to the intersection of NP and co-NP. Finally, the exact inclusion relationships between the classes P, NP and co-NP are presented.

Craig Alan Feinstein

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