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 25 for “"P-hard"”.
-
Computational complexity perspective on graphical calculi for quantum computation
… diagrams, the circuit extraction problem is #P-hard and unlikely to have an efficient algorithm. Therefore, partial solutions are critical. Currently, efficient circuit extraction is only possible for diagrams containing a structure of so-called Pauli flow. This structure is necessary and …
-
Measurement of Jet Constituent Yields in Pb-Pb Collisions at √sNN = 5.02 TeV Using the ALICE Detector
<p>Hard partonic scatterings serve as an important probe of quark-gluon-plasma (QGP) properties. The properties of jets and their constituents can provide a tool for understanding the partonic energy loss mechanisms. Low momentum jets offer a unique window into partonic energy loss because they …
-
Evaluation of relational algebra queries on probabilistic databases: tractability and approximation
… algebra queries with negation that separates #P-hard queries from those with PTIME data complexity. A framework for computing proba- bilities of relational algebra queries is presented; the probability computation algorithm is based on decomposition methods and provides exact answers in the case …
-
LOCATION AND ROUTING PROBLEMS: A UNIFIED APPROACH
… In particular three different types of N P -hard problems are taken into account: the first is an extension, arising in the context of waste collection management, of the well studied Vehicle Routing Problem. The second is based on the Multi-Depot Vehicle Routing Problem with profits and has …
-
Atomic Boson Sampling in a Bose-Einstein Condensed Gas
… two necessary ingredients of computational ♯P-hardness, squeezing and interference, are self-generated in the BEC gas and, contrary to Gaussian boson sampling in linear interferometers, external sources of squeezed bosons are not required for observation of quantum advantage manifestations. The …
-
Effects of heavy metals on the physical activity and survival of freshwater clams
<p>"Hard rock mining for valuable minerals can have negative impacts on the environment, both through the deposition of mine waste and through direct, physical impacts. The Bunker Hill Mine and other mines in/around Kellogg, ID produced approximately one-fifth of the nation's lead and zinc and …
-
Improving the capacity of radio spectrum: exploration of the acyclic orientations of a graph
… the chromatic polynomial is known to be #P-hard, but it is unknown whether or not the approximation at the value -1 is. There are two key contributions in this thesis. Firstly, we obtain computational results for all graphs with up to 8 vertices. We use the data to make observations on the …
-
Algorithms and computations in Khovanov homology
… with Khovanov homology is that it is much harder to compute. The three articles of this thesis study theoretical and algorithmic tools for computing Khovanov homology which are crucial for applying Khovanov homology to problems in low-dimensional topology and beyond. Article I employs a …
-
Biomimetic pneumatic soft actuator and microfluidic imaging system for analyzing nematodes locomotion
<p>Hard-bodied robots’ operations always are limited because of their rigid structures. Recently, researchers has been inspired by some animals because they can exhibit complex movement with soft structure. Conventional manipulators operate difficultly because of their rigid links in some highly …
-
Distributed anytime generic inference in valuation algebras
… <p>Exact inference in general is a #P-hard problem. Due to the prohibitive computational complexity, approximate inference is well-studied. In many applications a coarse approximation is sufficient. Ideally we would like such an approximation process to be anytime. In an anytime …
-
Physical properties of various conductive diborides and their binaries
<p>Hard, wear-resistant materials have potential utility as both coatings and bulk components in wear-prone applications. First-principle calculations performed by other investigators indicated that TaB2 and WB2 could be in the class of ultra-hard materials (hardness > 45 GPa), while MoB2 could be …
-
Price-setting Problems and Matroid Bayesian Online Selection
… a graphic matroid. In particular, it is PSPACE-hard to approximate the philosopher's expected revenue to some fixed constant α < 1; moreover, this cannot be alleviated by requirements on the arrival order in the case of graphic matroids. We also show similar hardness results for both transversal …
-
Development and Evaluation of Methodologies for Vulnerability Analysis of Ad-hoc Routing Protocols
… type of convex volume, which is known to be #P-hard. A new algorithm is derived, exploiting the particular problem structure, that can be used to reduce the amount of time used to compute these quantities over conventional algorithms. We show that timed-probabilistic formal models can be linked …
-
Pulsed laser deposition of AlMgB14 thin films
<p>Hard, wear-resistant coatings of thin film borides based on AlMgB14 have the potential to be applied industrially to improve the tool life of cutting tools and pump vanes and may account for several million dollars in savings as a result of reduced wear on these parts. Past work with this …
-
The complexity of graph polynomials
… 2. Evaluating S at a fixed point (u,v) is #P-hard unless uv=1 when there is a polynomial time algorithm.</p><p>Theorem 3. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers u and v, and evaluate …
-
Formulations and valid inequalities for Economic Lot Sizing Problems with Remanufacturing (ELSR)
… both. These problems have been proven to be N P-hard in general.Therefore, we study different approaches to tackle these problems.First, we propose several traditional methodologies to obtain better lowerf bounds for both problems, namely (?, S) - like inequalities and reformulation techniques, …
-
Approximation algorithms for NP-hard clustering problems
… each of these problems, it is known to be N P-hard to compute a solution with cost less than a certain constant factor times the optimal cost. We give simple constant-factor approximation algorithms for the facility location, k-median, and online median problems with optimal or near-optimal …
-
Preservation of determinism in MBQC under ZX-calculus rewrites
… that is equivalent to a ZX-diagram can be #P hard [11] - it is therefore important to look at the classes of ZX-diagrams that we have efficient circuit extraction algorithms for. The most general of these classes are ZX-diagrams with a property known as Pauli flow - this is a property from …
-
Dense subgraph mining in probabilistic graphs
… decomposition in probabilistic graphs? How hard is computing nucleus decomposition in probabilistic graphs? Can we devise efficient algorithms for exact or approximate nucleus decomposition in large graphs? We present three natural definitions of nucleus decomposition in probabilistic …
-
Code-based Cryptography: Attacking and Constructing Cryptographic Systems
… of view, code-based assumptions are oftenN P-hard computational problems, which have been the staples for provably-secured systems. On the other hand, cryptanalysis algorithms have witnessedsignificant advancements, employing increasingly more sophisticated techniques. Yet, the fundamental …
Page 1 of 2