Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"NP Completeness"”.
-
NP-completeness notions under strong hypotheses
A variety of completeness notions for the complexity class NP are studied under strong hypotheses about the size of this class. These hypotheses are based on the concept of resource-bounded genericity developed by Ambos-Spies, Fleischhack and Huwig. It is shown that many natural completeness …
-
An Interactive Tutorial for NP-Completeness
… Complexity Theory, reductions, and the NP-Complete class of problems are considered difficult by students. Numerous algorithm visualizations (AVs) have been developed over the years to portray the dynamic nature of known algorithms commonly taught in undergraduate classes. However, to …
-
Physical manifestation of NP-completeness in analog computer devices
Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1999.
-
Minimal PMU placement for graph observability: a decomposition approach
… such that the entire graph is observed. The NP-completeness of PMU placement for planar bipartite graphs is shown. PMU placement algorithms are developed for graphs of bounded tree width, such as trees and outer planar graphs. Graph decompositions are used to develop efficient algorithms that …
-
Some results on symmetric signings
… with specific spectral properties. We show NP-completeness for verifying whether an arbitrary matrix has a symmetric signing that is positive semi-definite, is singular, or has bounded eigenvalues. We exhibit a stark contrast between invertibility and the above-mentioned spectral properties …
-
Fundamentals and applications of order dependencies
… of order dependency classes; (iii) a proof of co-NP-completeness of the inference problem for ODs and for the subclass of UODs; (iv) a proof of co-NP-completeness of the inference problem of functional dependencies (FDs) from ODs in general, but demonstrate linear time complexity for the inference …
-
Fine-grained complexity meets communication complexity
… similar approximation hardness in the world of NP-completeness, is not fine-grained enough to yield interesting conditional lower bounds for approximation problems in P.
-
Problems in Sorting and Graph Algorithms
… conjecture that every sorting algorithm on some input involves every key in O(log n) comparisons. We give partial results. The third problem concerns finding efficient algorithms for finding cycles of small fixed length in graphs. We give algorithms for general graphs and O(n log n) algorithms for …
-
Complexity of minesweeper with restricted number
… problems. We prove either inclusion in P or NP-completeness for the restricted-set Minesweeper consistency problem for 134 of the 512 subsets of the set of numbers above. In particular, we show that {0,1}-Minesweeper consistency is NP-complete, while {0}-Minesweeper consistency and …
-
Square Root Finding In Graphs
… of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with …
-
A framework for proving the computational intractability of motion planning problems
… algorithms and hardness results ranging from NL-completeness to Undecidability. Full dichotomies are obtained for some classes including the natural class of gadgets which can be traversed a bounded number of times. For 1-player this gives a separation between containment in NL versus …
-
New Algorithms andMethodology for Analysing Distances
… the assignment metric. We then prove some new NP-completeness results for problems using two related “sum-of-squares” clustering criteria. Closely related to partitional clustering is the problem of hierarchical clustering. We extend and formalise this problem to the problem of constructing …
-
Algorithms for DFM in electronic design automation
… characters. 2D stencil planning is proved NP-Hard. With the assumption of standard cells, the 2D problem can be partitioned into 1D row ordering subproblems; however, it is also considered hard, and no efficient optimal solution has been provided so far. We propose a polynomial time optimal …
-
Solving Hybrid Boolean SAT by Continuous Optimization
… importance in computer science. Despite the NP-completeness of SAT, progress on the engineering side—especially that of Conflict-Driven Clause Learning (CDCL) and Local Search SAT solvers—has been remarkable. Yet, while SAT solvers, aimed at solving industrial-scale benchmarks in Conjunctive …
-
SET THEORY FOR KNOWLEDGE REPRESENTATION
The decision problem in set theory has been intensively investigated in the last decades, and decision procedures or proofs of undecidability have been provided for several quantified and unquantified fragments of set theory. In this thesis we study the decision problem for three novel quantified …
-
Model-checking problems, machines and parameterized complexity
… intractable, <br>which resembles the classical NP-completeness theory. <br>However almost all <br>those classes are defined as closures of kernel problems <br>under some type of reductions. <br> <br>The main topic of our thesis is to provide natural machine <br>characterizations of all major …
-
Preference inference based on lexicographic and Pareto models
… efficient algorithms; for others we show NP-completeness and coNP-completeness results. In particular, we find that the Deduction and Consistency problem are polynomial time solvable for comparative preference statements for lexicographic and simple Pareto preference models by a detailed …
-
On Reducing Delays in P2P Live Streaming Systems
… We formulate the MDPS problem and prove its NP-completeness. We then present a polynomial-time approximation algorithm, called Fastream-I, for this problem, and show that the performance of Fastream-I is bounded by a ratio of O(SQRT(log n)), where n is the number of peers in the system. We …
-
A complete complexity taxonomy of ‘small’ fragments of theory Multi-Level Syllogistic
… soddisfacibili in tempo polinomiale e frammenti NP-completi.
-
ΠΡΟΒΛΗΜΑΤΑ ΣΥΝΤΟΝΙΣΜΟΥ ΤΑΥΤΟΧΡΟΝΩΝ ΠΡΟΣΠΕΛΑΣΕΩΝ ΣΕ ΒΑΣΕΙΣ ΔΕΔΟΜΕΝΩΝ
… SERIALIZABILITY (CSR). WE PROVE THAT IT IS NP-COMPLETE TO DECIDE WHETHER A SET OF SCHEDULES IS ON-LINE SCHEDULABLE (OLS). WE INTRODUCE THE CONCEPT OF MAXIMAL OLS SETS AND SHOW THAT NO EFFICIENT SCHEDULER CAN BEDESGNED THAT RECOGNIZES MAXIMAL SUBSETS OF MVSR OR MVCSR. FINALLY A GENERAL …