Wyniki wyszukiwania - BazTech

1

Applying Modern SAT-solvers to Solving Hard Problems

Niewiadomski Artur, Switalski Piotr, Sidoruk Teofil, Penczek Wojciech

Fundamenta Informaticae

|

2019

|

Vol. 165, nr 3-4

321--344

EN

We present nine SAT-solvers and compare their efficiency for several decision and combinatorial problems: three classical NP-complete problems of the graph theory, bounded Post correspondence problem (BPCP), extended string correction problem (ESCP), two popular chess problems, PSPACE-complete verification of UML systems, and the Towers of Hanoi (ToH) of exponential solutions. In addition to several known reductions to SAT for the problems of graph k-colouring, vertex k-cover, Hamiltonian path, and verification of UML systems, we also define new original reductions for the N-queens problem, the knight’s tour problem, and ToH, SCP, and BPCP. Our extensive experimental results allow for drawing quite interesting conclusions on efficiency and applicability of SAT-solvers to different problems: they behave quite efficiently for NP-complete and harder problems but they are by far inferior to tailored algorithms for specific problems of lower complexity.

2

On The Complexity of Counter Reachability Games

Reichert J.

Fundamenta Informaticae

|

2016

|

Vol. 143, nr 3/4

415--436

EN

Counter reachability games are played by two players on a graph with labelled edges. Each move consists of picking an edge from the current location and adding its label to a counter vector. The objective is to reach a given counter value in a given location. We distinguish three semantics for counter reachability games, according to what happens when a counter value would become negative: the edge is either disabled, or enabled but the counter value becomes zero, or enabled. We consider the problem of determining the winner in counter reachability games and show that, in most cases, it has the same complexity under all semantics. This constrasts with the one-player case, for which the decision problem is decidable without any elementary upper bound under the first semantics, whereas it is NP-complete under the third one. Surprisingly, under one semantics, the complexity in dimension one depends on whether the objective value is zero or any other integer.

3

Poszukiwanie rozwiązań problemu plecakowego z wykorzystaniem algorytmu genetycznego

Handzel Z., Gajer M.

Elektronika : konstrukcje, technologie, zastosowania

|

2014

|

Vol. 55, nr 2

45-46

PL

Tematyka artykułu dotyczy wykorzystania techniki obliczeniowej opartej na zastosowaniu algorytmów genetycznych na potrzeby rozwiązania zagadnienia plecakowego. W artykule zaproponowano wykorzystanie binarnego sposobu kodowania rozwiązań na materiale genetycznym ewoluujących osobników. Szerzej omówiono zagadnienia związane z obliczaniem wartości funkcji dopasowania i realizacją operacji selekcji turniejowej.

EN

The topic of the paper is about using computational technique based on genetic algorithms for the purpose of rucksack problem solution. In the paper we propose to use binary system of coding of the solutions on the genetic material of evolving individuals. We discuss in detail the issues related to calculating the values of fitness function and realizations of tournament selection.

4

Solving SUBSET SUM by Spiking Neural P Systems with Pre-computed Resources

Leporati A., Gutiérrez-Naranjo M.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 1

61-77

EN

Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre–computed resources are given in advance, provided that their structure is “regular” and they do not contain neither “hidden information” that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as SUBSET SUM. In particular, we first propose a semi–uniform family of spiking neural P systems in which every system solves a specific instance of SUBSET SUM. Then, we exploit a technique used to calculate ITERATED ADDITION with Boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve any instance of SUBSET SUM of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size.

5

On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution

Zandron C., Leporati A., Ferretti C., Mauri G., Pérez-Jiménez M.J.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 1

79-91

EN

Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximallly parallel way.

6

A note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphs

Monnot J.

Foundations of Computing and Decision Sciences

|

2006

|

Vol. 31, No. 2

169-173

EN

The precoloring extension coloring problem consists in deciding, given a positive integer k, a graph G = (V,E] and k pairwise disjoint subsets Vo, ..., Vk-1 of V, if there exists a (vertex) coloring S = (So,...,Sk-i) of G such that Vi ⊇ Si, for all i = 0,...,k-1:— 1. In this note, we show that the precoloring extension coloring problem is NP-complete in triangle free planar graphs with maximum degree 4.

7

Some aspects of ant systems for the TSP

Boryczka M.

Fundamenta Informaticae

|

1998

|

Vol. 35, nr 1-4

197-209

EN

We describe the ant systems and the application of the generative policies improving the performance of the ant systems in the context of the Travelling salesman Problem. The generative policies are derived from the studies carried out in Germany and USA in the sixties. We study the leader (superman) and elite strategies, which have been chosen because of their analogy to the world of real ants. First, we describe three ant algorithms and we introduce a formal description of the ant system. Then we discuss the reflection of the evolutionary computing in the ant systems.