4,585 research outputs found
Solving NP-SPEC Domains Using ASP
No full textNP-SPEC is a language for specifying problems in NP in a declarative way. Despite the fact that the semantics of the language was given by referring to Datalog with circumscription, which is very close to ASP, so far the only existing implementations are by means of ECLiPSe Prolog and via Boolean satisfiability solvers. In this paper, we present translations from NP-SPEC into various forms of ASP, and provide an experimental evaluation of existing implementations and the proposed translations to ASP using various ASP solvers. We also argue that it might be useful to incorporate certain language constructs of NP-SPEC into mainstream ASP
Effectively Solving NP-SPEC Encodings by Translation to ASP
No full textNP-SPEC is a language for specifying problems in NP in a declarative way. Despite the fact that the semantics of the language was given by referring to Datalog with circumscription, which is very close to ASP, so far the only existing implementations are by means of ECLiPSe Prolog and via Boolean satisfiability solvers. In this paper, we present translations from NP-SPEC into ASP, and provide an experimental evaluation of existing implementations and the proposed translations to ASP using various ASP solvers. The results show that translating to ASP clearly has an edge over the existing translation into SAT, which involves an intrinsic grounding process. We also argue that it might be useful to incorporate certain language constructs of NPSPEC into mainstream ASP
A constraint programming approach to the stable marriage problem
No full textThe Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an instance I of SM as an instance J of a Constraint Satisfaction Problem. We prove that, in a precise sense, establishing arc consistency in J is equivalent to the action of the established Extended Gale/Shapley algorithm for SM on I. As a consequence of this, the man-optimal and woman-optimal stable matchings can be derived immediately. Furthermore we show that, in both encodings, all solutions of I may be enumerated in a failure-free manner. Our results indicate the applicability of Constraint Programming to the domain of stable matching problems in general, many of which are NP-hard
Numerical evidence for phase transitions of NP-complete problems for instances drawn from Lévy-stable distributions
No full textRandom NP-Complete problems have come under study as an important tool used in the analysis
of optimization algorithms and help in our understanding of how to properly address issues of
computational intractability.
In this thesis, the Number Partition Problem and the Hamiltonian Cycle Problem are taken as
representative NP-Complete classes. Numerical evidence is presented for a phase transition in the
probability of solution when a modified Lévy-Stable distribution is used in instance creation for each.
Numerical evidence is presented that show hard random instances exist near the critical threshold
for the Hamiltonian Cycle problem. A choice of order parameter for the Number Partition Problem’s
phase transition is also given.
Finding Hamiltonian Cycles in Erdös-Rényi random graphs is well known to have almost sure polynomial time algorithms, even near the critical threshold. To the author’s knowledge, the graph
ensemble presented is the first candidate, without specific graph structure built in, to generate
graphs whose Hamiltonicity is intrinsically hard to determine. Random graphs are chosen via their
degree sequence generated from a discretized form of Lévy-Stable distributions. Graphs chosen from
this distribution still show a phase transition and appear to have a pickup in search cost for the
algorithms considered. Search cost is highly dependent on the particular algorithm used and the
graph ensemble is presented only as a potential graph ensemble to generate intrinsically hard graphs
that are difficult to test for Hamiltonicity.
Number Partition Problem instances are created by choosing each element in the list from a modified
Lévy-Stable distribution. The Number Partition Problem has no known good approximation algorithms and so only numerical evidence to show the phase transition is provided without considerable
focus on pickup in search cost for the solvers used. The failure of current approximation algorithms
and potential candidate approximation algorithms are discussed
np-CECADA: Enhancing Ubiquitous Connectivity of LoRa Networks
No full textLong Range Wide Area Networks (LoRaWAN) offer ubiquitous communications for The Internet of Things (IoT). However, there are many challenges in rolling out LoRaWAN - mainly scalability, energy efficiency, Packet Reception Ratio (PRR), and keeping the channel access as simple as unslotted ALOHA. To this end, we design non-persistent Capture Effect Channel Activity Detection Algorithm (np-CECADA), which is a novel, distributed protocol for the MAC layer of LoRaWAN. It utilizes Channel Activity Detection (CAD), which is a built-in imperfect mechanism for channel sensing and minimal feedback from the gateways. In np-CECADA each device independently adapts backoff times based on the traffic in its vicinity and the transmission power based on the heuristically inferred probability of capturing the channel. To achieve this, first, we carried out an extensive on-field evaluation to measure the effectiveness of CAD and capture effect in LoRa. Using them we designed np CECADA and developed ns-3 modules. Packet Reception Ratio of np-CECADA is 15.74× and 5.13× higher than vanilla LoRaWAN and p-CARMA, respectively. Channel utilization is 11.24× higher compared to LMAC. Further, on a testbed of 30 LoRa devices np-CECADA outperforms LoRaWAN up to 5 times.Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Embedded System
Manipulability of Single Transferable Vote
No full textFor many voting rules, it is NP-hard to compute a successful manipulation.
However, NP-hardness only bounds the worst-case complexity. Recent
theoretical results suggest that manipulation may often be easy in practice. We
study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice
On the decidability of connectedness constraints in 2D and 3D Euclidean spaces
No full textWe investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in the Euclidean plane, NP-complete over regular closed sets in three-dimensional Euclidean space, and ExpTime-complete over polyhedra in three-dimensional Euclidean space
Beyond NP: the QSAT phase transition
No full textWe show that phase transition behaviour similar to that observed in NP-complete problems like random 3-Sat occurs in Pspace-complete problems like random Qsat. Most of the differences in phase transition behaviour that Cadoli et al. report for random Qsat problems (for instance, no fixed point and no easy-hard-easy pattern) are largely due to the presence of trivially unsatisfiable problems. Once they are removed, we see behaviour more familiar to us from Sat and other NP-complete domains. There do, however, appear to be some slight differences. When problems contain short clauses, there is a large gap between worst case behaviour and median, and the easy-hard-easy pattern is restricted to the higher percentiles of the search cost. In addition, our theory of constrainedness appears to be rather less accurate at predicting the precise location of the phase transition compared to many NP-complete problems. We conjecture that the accuracy may be influenced by the super-exponential size of..
Unweighted coalitional manipulation under the Borda rule is NP-hard
No full textThe Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result
P≠NP
No full textHere, the author tries to build the structure of the Theory of computation based on considering time as a fuzzy concept.
In fact, there are reasons to consider time as a fuzzy concept. In this article, the author doesn’t go to this side but note that Brower and Husserl views on the concept of time were similar [8]. Some reasons have been given for it in [3].
Throughout this article, the author presents the Theory of Computation with Fuzzy Time. Given the classic definition of Turing Machine, the concept of Time is modified to Fuzzy time. This new term calls as Theory TC* [2] and this type of computation “Fuzzy time Computation”. We have relatively large number of fundamental unsolved problems in Complexity Theory. In the new theory, some of the major obstacles and unsolved problems have been solved [2]. It should be noted that in this article, the writer considers fuzzy number associated to instants of time as a symmetric one. The point about the symmetry is in the proof of Lemma 3, although it is generalizable.
In particular, the new classes of complexity Theory, P*, NP*, BPP* in the TC* analogues to the definitions of P, NP, BPP defines as their natural alternative definition. Here, we will see P*≠ NP*, P*= BPP*. Finally, we have Theorem 4
- …
