Results 11 to 20 of about 272,983 (311)
NP-completeness: A retrospective [PDF]
, 1997 For a quarter of a century now, NP-completeness has been computer science's favorite paradigm, fad, punching bag, buzzword, alibi, and intellectual export. This paper is a fragmentary commentary on its origins, its nature, its impact, and on the attributes that have made it so pervasive and contagious.
Christos H. Papadimitriou
openaire +2 more sources
From NP-Completeness to DP-Completeness: A Membrane Computing Perspective
Complexity, 2020 Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ ...
Luis Valencia-Cabrera +4 more
doaj +1 more source
CoRR, 2021 We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1 tiles. Such a puzzle is defined by a set of unit-square 1 tiles in a square grid, and a target square of the grid. A move consists of selecting an unselected 1 tile and then filling the next unfilled square in a chosen direction from that tile (similar to Tipover and Cross ...
Sagnik Saha, Erik D. Demaine
openaire +2 more sources
Universal First-Order Logic is Superfluous for NL, P, NP and coNP [PDF]
Logical Methods in Computer Science, 2014 In this work we continue the syntactic study of completeness that began with the works of Immerman and Medina. In particular, we take a conjecture raised by Medina in his dissertation that says if a conjunction of a second-order and a first-order ...
Nerio Borges, Blai Bonet
doaj +1 more source
New Results on Generalized Graph Coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2004 For graph classes \wp_1,...,\wp_k, Generalized Graph Coloring is the problem of deciding whether the vertex set of a given graph G can be partitioned into subsets V_1,...,V_k so that V_j induces a graph in the class \wp_j (j=1,2,...,k).
Vladimir E. Alekseev +2 more
doaj +1 more source
P_4-Colorings and P_4-Bipartite Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 A vertex partition of a graph into disjoint subsets V_is is said to be a P_4-free coloring if each color class V_i induces a subgraph without chordless path on four vertices (denoted by P_4).
Chinh T. Hoàng, Van Bang Le
doaj +1 more source
NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3
Моделирование и анализ информационных систем, 2021 In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or (k +
Alexander Valeryevich Smirnov
doaj +1 more source
Graphs of intersections of closed polygonal chains
Журнал Белорусского государственного университета: Математика, информатика, 2021 In the paper such subclass of string graphs as intersection graphs of closed polygonal chains (class of CPC-graphs) was considered, necessary conditions for belonging to that class, forbidden subgraphs and operations with graphs which preserve belonging ...
Nikolai P. Prochorov, Ekaterina N. Dul
doaj +1 more source
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions [PDF]
Quantum, 2020 A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions.
Nai-Hui Chia, Sean Hallgren, Fang Song
doaj +1 more source
Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective
Mathematics, 2023 The clique transversal problem and its variants have garnered significant attention in the last two decades due to their practical applications in communication networks, social-network theory and transceiver placement for cellular telephones.
Chuan-Min Lee
doaj +1 more source