Wyniki wyszukiwania - Biblioteka Nauki

1

Computational Complexity of NURIKABE

100%

Holzer M. , Klein A. , Kutrib M. , Ruepp O.

|

2011

|

tom Vol. 110, nr 1-4

159-174

EN

We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.

2

Polynomially Bounded Sequences and Polynomial Sequences

100%

Okazaki H. , Futa Y.

Formalized Mathematics

|

2015

|

tom 23

|

nr 3

205-213

EN

In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental computational complexity class that contains all polynomial-time decision problems [11], [12]. It takes polynomially bounded amount of computation time to solve polynomial-time decision problems by the deterministic Turing machine. Moreover we formalize polynomial sequences [5].

3

Hardness Results for Total Rainbow Connection of Graphs

100%

Chen L. , Huo B. , Ma Y.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 2

355-362

EN

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring of a graph G makes it total rainbow connected is NP-Complete. We also prove that given a graph G, deciding whether trc(G) = 3 is NP-Complete.

4

Computational Complexity of Simple P Systems

80%

Ciobanu G. , Resios A.

|

2008

|

tom Vol. 87, nr 1

49-59

EN

This paper introduces a new class of membrane systems called simple P systems, and studies their computational complexity. We start by presenting the knapsack problem and its time complexity. Then we study the computational complexity of simple P systems by considering the allocation of resources enabling the parallel application of the rules. We show that the decision version of the resource allocation problem for simple P systems is NP-complete, by using the knapsack problem.

5

Proof Compression and NP Versus PSPACE II: Addendum

80%

Gordeev L. , Haeusler E. H.

Bulletin of the Section of Logic

|

2022

|

tom 51

|

nr 2

197-205

EN

In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic (HSC) with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction (ND). In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea (due to the second author) is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSC-elimination from our proof of NP = PSPACE.

6

Automata-Theoretic Decision Procedures for Information Logics

80%

Demri S. , Sattler U.

|

2002

|

tom Vol. 53, nr 1

1-22

EN

Automata-theoretic decision procedures for solving model-checking and satisfiability problems for temporal, dynamic, and description logics have flourished during the past decades. In the paper we define an EXPTIME decision procedure based on the emptiness problem of Büchi automata on infinite trees for the very expressive information logic SIM designed for reasoning about information systems. This logic involves modal parameters satisfying certain properties to capture the relevant nominals at the formula level, Boolean expressions and nominals at the modal level, an implicit intersection operation for relations, and a universal modality. The original combination of known techniques allows us to solve the open question related to the EXPTIME -completeness of SIM. Furthermore, we discuss how variants of SIM can be treated similarly although the decidability status of some of them is still unknown.

7

Relative Nondeterministic Information Logic is EXPTIME-complete

80%

Demri S. , Orłowska E.

|

2007

|

tom Vol. 75, nr 1-4

163-178

EN

We define a relative version of the logic NIL introduced by Or owska, Pawlak and Vakarelov and we show that its satisfiability is not only decidable but also EXPTIME-complete. Such a logic combines two ingredients that are seldom present simultaneously in information logics: frame conditions involving more than one information relation and relative frames. The EXPTIMEupper bound is obtained by designing a well-suited decision procedure based on the nonemptiness problem of Büchi automata on infinite trees. The paper provides evidence that Büchi automata on infinite trees are crucial language acceptors even for relative information logics with multiple types of relations.

8

On the Optimality of the Binary Algorithm for the Jacobi Symbol

80%

Busch J.

|

2007

|

tom Vol. 76, nr 1-2

1-11

EN

We establish lower bounds on the complexity of computing the following number-theoretic functions and relations from piecewise linear primitives: (i) the Legendre and Jacobi symbols, (ii) pseudoprimality, and (iii) modular exponentiation. As a corollary to the lower bound obtained for (i), an algorithm of Shallit and Sorenson is optimal (up to a multiplicative constant).

9

Proof Compression and NP Versus PSPACE II

80%

Gordeev L. , Haeusler E. H.

Bulletin of the Section of Logic

|

2020

|

tom 49

|

nr 3

213-230

EN

We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suﬃces to show that every valid purely implicational formula ρ has a proof whose weight (= total number of symbols) and time complexity of the provability involved are both polynomial in the weight of ρ. As is [3], we use proof theoretic approach. Recall that in [3] we considered any valid ρ in question that had (by the deﬁnition of validity) a “short” tree-like proof π in the Hudelmaier-style cutfree sequent calculus for minimal logic. The “shortness” means that the height of π and the total weight of diﬀerent formulas occurring in it are both polynomial in the weight of ρ. However, the size (= total number of nodes), and hence also the weight, of π could be exponential in that of ρ. To overcome this trouble we embedded π into Prawitz’s proof system of natural deductions containing single formulas, instead of sequents. As in π, the height and the total weight of diﬀerent formulas of the resulting tree-like natural deduction ∂1 were polynomial, although the size of ∂1 still could be exponential, in the weight of ρ. In our next, crucial move, ∂1 was deterministically compressed into a “small”, although multipremise, dag-like deduction ∂ whose horizontal levels contained only mutually diﬀerent formulas, which made the whole weight polynomial in that of ρ. However, ∂ required a more complicated veriﬁcation of the underlying provability of ρ. In this paper we present a nondeterministic compression of ∂ into a desired standard dag-like deduction ∂0 that deterministically proves ρ in time and space polynomial in the weight of ρ.2 Together with [3] this completes the proof of NP = PSPACE.Natural deductions are essential for our proof. Tree-to-dag horizontal compression of π merging equal sequents, instead of formulas, is (possible but) not suﬃcient, since the total number of diﬀerent sequents in π might be exponential in the weight of ρ – even assuming that all formulas occurring in sequents are subformulas of ρ. On the other hand, we need Hudelmaier’s cutfree sequent calculus in order to control both the height and total weight of diﬀerent formulas of the initial tree-like proof π, since standard Prawitz’s normalization although providing natural deductions with the subformula property does not preserve polynomial heights. It is not clear yet if we can omit references to π even in the proof of the weaker result NP = coNP.

10

Nets with Tokens which Carry Data

80%

Lazić R. , Newcomb T. , Ouaknine J. , Roscoe A. W. , Worrell J.

|

2008

|

tom Vol. 88, nr 3

251-274

EN

We study data nets, a generalisation of Petri nets in which tokens carry data from linearlyordered infinite domains and in which whole-place operations such as resets and transfers are possible. Data nets subsume several known classes of infinite-state systems, including multiset rewriting systems and polymorphic systems with arrays. We show that coverability and termination are decidable for arbitrary data nets, and that boundedness is decidable for data nets in which whole-place operations are restricted to transfers. By providing an encoding of lossy channel systems into data nets without whole-place operations, we establish that coverability, termination and boundedness for the latter class have non-primitive recursive complexity. The main result of the paper is that, even for unordered data domains (i.e., with only the equality predicate), each of the three verification problems for data nets without whole-place operations has non-elementary complexity.

11

One Pebble Versus e log n Bits

80%

Geffer V. , Mereghetti C. , Pighizzin G.

|

2010

|

tom Vol. 104, nr 1/2

55-69

EN

We show that, for any ε> 0, there exists a language accepted in strong ĺźlog n space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e., a 2-way nondeterministic Turing machine with one pebble that can be moved onto the input cells). Moreover, we provide optimal unary lower bounds on the product of space and input head reversals for strong and weak pebble machines accepting nonregular languages.

12

On the Computational Complexity of Matrix Semigroup Problems

80%

Bell P. C. , Potapov I.

|

2012

|

tom Vol. 116, nr 1-4

1-13

EN

Most computational problems for matrix semigroups and groups are inherently difficult to solve and even undecidable starting from dimension three. The questions about the decidability and complexity of problems for two-dimensional matrix semigroups remain open and are directly linked with other challenging problems in the field. In this paper we study the computational complexity of the problem of determining whether the identity matrix belongs to a matrix semigroup (the Identity Problem) generated by a finite set of 2 × 2 integral unimodular matrices. The Identity Problem for matrix semigroups is a well-known challenging problem, which has remained open in any dimension until recently. It is currently known that the problem is decidable in dimension two and undecidable starting from dimension four. In particular, we show that the Identity Problem for 2 × 2 integral unimodular matrices is NP-hard by a reduction of the Subset Sum Problem and several new encoding techniques. An upper bound for the nontrivial decidability result by C. Choffrut and J. Karhum¨aki is unknown. However, we derive a lower bound on the minimum length solution to the Identity Problem for a constructible set of instances, which is exponential in the number of matrices of the generator set and the maximal element of the matrices. This shows that the most obvious candidate for an NP algorithm, which is to guess the shortest sequence of matrices which multiply to give the identity matrix, does not work correctly since the certificate would have a length which is exponential in the size of the instance. Both results lead to a number of corollaries confirming the same bounds for vector reachability, scalar reachability and zero in the right upper corner problems.

13

Computing Issues of Asynchronous CA

80%

Dennunzio A. , Formenti E. , Manzoni L.

|

2012

|

tom Vol. 120, nr 2

165-180

EN

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.

14

The NP-completeness of automorphic colorings

80%

Mazzuoccolo G.

Discussiones Mathematicae Graph Theory

|

2010

|

tom 30

|

nr 4

705-710

EN

Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.

15

Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

80%

Dereniowski D.

Discussiones Mathematicae Graph Theory

|

2009

|

tom 29

|

nr 2

253-261

EN

A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410] that the decision problem: given a simple graph G, decide whether there exists a spanning tree T of G such that T has a vertex 4-ranking, is NP-complete. In this paper we improve this result by proving NP-hardness of finding for a given chordal graph its spanning tree having vertex 3-ranking. This bound is the best possible. On the other hand we prove that MVRST problem can be solved in linear time for proper interval graphs.

16

On the computational complexity of (O,P)-partition problems

80%

Kratochvíl J. , Schiermeyer I.

Discussiones Mathematicae Graph Theory

|

1997

|

tom 17

|

nr 2

253-258

EN

We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.

17

Partial covers of graphs

80%

Fiala J. , Kratochvíl J.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 1

89-99

EN

Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of deciding existence of partial covers and of full covers (locally bijective homomorphisms), which were previously studied.

18

The nondeterministic information logic NIL is PSPACE-complete

80%

Demri S.

|

2000

|

tom Vol. 42, nr 3,4

211-234

EN

The nondeterministic information logic NIL has been introduced by Or owska and Pawlak in 1984 as a logic for reasoning about total information systems with the similarity, the forward inclusion and the backward inclusion relations. In 1987, Vakarelov provides the first first-order characterization of structures derived from information systems and this has been done with the semantical structures of NIL. Since then, various extensions of NIL have been introduced and many issues for information logics about decidability and Hilbert-style proof systems have been solved. However, computational complexity issues have been seldom attacked in the literature mainly because the information logics are propositional polymodal logics with interdependent modal connectives. We show that NIL satisfiability is a PSPACE-complete problem. PSPACE-hardness is shown to be an easy consequence of PSPACE-hardness of the well-known modal logic S4. The main difficulty is to show that NIL satisfiability is in PSPACE. To do so we present an original construction that extends various previous works by Ladner (1977), Halpern and Moses (1992) and Spaan (1993).

19

Complexity of fuzzy probability logics

80%

Hajek P. , Tulipani S.

|

2001

|

tom Vol. 45, nr 3

207-213

EN

The satisfiability problem for the logic FP() (fuzzy probability logic over ukasiewicz logic) is shown to be NP-complete; satisfiability in FP(P) (the same over the logic joining ukasiewicz and product logic) is shown to be in PSPACE.

20

On the Computational Complexity of Optimal Multisplitting

80%

Elomaa T. , Rousu J.

|

2001

|

tom Vol. 47, nr 1,2

35-52

EN

The need to partition or discretize numeric value ranges arises in machine learning and data mining algorithms. This subtask is a potential time-consumption bottleneck, since the number of candidate partitions is exponential in the number of possible cut points in the range. Thus, many heuristic algorithms have been proposed for this task. Recently, the efficiency of optimal multisplitting has improved dramatically, due to the introduction of linear-time algorithms for training error minimization and quadratic-time generic algorithms. Whether these efficient algorithms are the best obtainable, is not yet known. In this paper, we probe the inherent complexity of the multisplitting problem. We reflect results obtained for similar problems in computational geometry and string matching to the multisplitting task. Subquadratic optimization algorithms in computational geometry rely on the monotonicity of the optimized function. We show by counterexamples that the widely used evaluation functions Training Set Error and Average Class Entropy do not satisfy the kind of monotonicity that facilitates subquadratic-time optimization. However, we also show that the Training Set Error function can be decomposed into monotonic subproblems, one per class, which explains its linear time optimization. Finally, we review recently developed techniques for speeding up optimal multisplitting.