Generation problems
| Autor: | B. Schwarz, Christian Glaßer, Klaus W. Wagner, Elmar Böhler |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Class (set theory)
General Computer Science Computational complexity theory SOS problem Polynomials Upper and lower bounds Theoretical Computer Science Computational complexity Combinatorics Bivariate polynomials Closure (computer programming) Binary operation Closures Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 345(2-3):260-295 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2005.07.011 |
| Popis: | Given a fixed computable binary operation f, we study the complexity of the following generation problem: the input consists of strings a1, ..., an, b. The question is whether b is in the closure of {a1, ..., an} under operation f.For several subclasses of operations we prove tight upper and lower bounds for the generation problems. For example, we prove exponential-time upper and lower bounds for generation problems of length-monotonic polynomial-time computable operations. Other bounds involve classes like NP and PSPACE.Here, the class of bivariate polynomials with positive coefficients turns out to be the most interesting class of operations. We show that many of the corresponding generation problems belong to NP. However, we do not know this for all of them, e.g., for x2 + 2y this is an open question. We prove NP-completeness for polynomials xaybc where a, b, c ≥ 1. Also, we show NP-hardness for polynomials like x2 + 2y. As a by-product we obtain NP-completeness of the extended sum-of-subset problem SOSc = {(w1, ..., wn, z) : ∃I ⊆ {1, ..., n}(Σi∈I wic = z)} for any c ≥ 1. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect