Arrow Research search

Author name cluster

Marek Piotrów

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
2 author rows

Possible papers

8

SAT Conference 2020 Conference Paper

Incremental Encoding of Pseudo-Boolean Goal Functions Based on Comparator Networks

  • Michal Karpinski
  • Marek Piotrów

Abstract Incremental techniques have been widely used in solving problems reducible to SAT and MaxSAT instances. When an algorithm requires making subsequent runs of a SAT-solver on a slightly changing input formula, it is usually beneficial to change the strategy, so that the algorithm only operates on a single instance of a SAT-solver. One way to do this is via a mechanism called assumptions, which allows to accumulate and reuse knowledge from one iteration to the next and, in consequence, the provided input formula need not to be rebuilt during computation. In this paper we propose an encoding of a Pseudo-Boolean goal function that is based on sorting networks and can be provided to a SAT-solver only once. Then, during an optimization process, different bounds on the value of the function can be given to the solver by appropriate sets of assumptions. The experimental results show that the proposed technique is sound, that is, it increases the number of solved instances and reduces the average time and memory used by the solver on solved instances.

Details

MFCS Conference 1994 Conference Paper

Reliable Minimum Finding Comparator Networks

  • Piotr Denejko
  • Krzysztof Diks
  • Andrzej Pelc
  • Marek Piotrów

Abstract We consider the problem of constructing reliable minimum finding networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. Our main result is the first nontrivial lower bound on depths of networks computing minimum among n > 2 items in the presence of k > 0 faulty comparators. We prove that the depth of any such network is at least max([log n ] + 2 k, log n + k log log n/k +1). We also describe a network whose depth nearly matches the lower bound. The lower bounds should be compared with the first nontrivial upper bound O (log n + k log log n /log k ) on the depth of k -fault tolerant sorting networks that was recently derived by Leighton and Ma [6].

Details

MFCS Conference 1990 Conference Paper

ATIME(N) is Closed Under Counting

  • Marek Piotrów

Abstract It has been recently found out that different variations of counting play an important role in structural complexity theory (for example, it has been argued that the ability of counting is closely related with the ability of nondeterministic complementation). In this paper it is proved that ATIME( T(n) ) classes, for T(n) ≥ n, are closed under counting. Thus exponentially many words, each of size O( n ), can be counted by an alternating Turing machine in the optimal time O( n ).

Details

MFCS Conference 1988 Conference Paper

On Complexity of Counting

  • Marek Piotrów

Abstract Let l, u: ℕ→ℕ, l<u. We give a full characterization of intervals [ l, u ] such that a polynomial-time ATM of a constant numer of alternations can verify the number of words of a given length and in a given (as its oracle) set A, provided that A 's density function is in [ l, u ]. We prove also a new lower bound on the approximate counting: there is a recursive set A whose elements cannot be approximate counted in Σ p, A 2 ∪ Π p, A 2.

Details