Journal articles: 'NP-complexity'

1

Vardi, Moshe Y. "On P, NP, and computational complexity." Communications of the ACM 53, no. 11 (November 2010): 5. http://dx.doi.org/10.1145/1839676.1839677.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

de Haan, Ronald, and Stefan Szeider. "Parameterized complexity classes beyond para-NP." Journal of Computer and System Sciences 87 (August 2017): 16–57. http://dx.doi.org/10.1016/j.jcss.2017.02.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Jiang, Yaozhi. "A Proof “P≠NP” for P vs. NP Problem by Multiple-Tape Turing-Machine." Journal of Mathematics Research 12, no. 4 (July 7, 2020): 1. http://dx.doi.org/10.5539/jmr.v12n4p1.

Full text

Abstract:

P vs. NP problem is very important research direction in computation complexity theory. In this paper author, by an engineer’s viewpoint, establishes universal multiple-tape Turing-machine and k-homogeneous multiple-tape Turing-machine, and by them we can obtain an unified mathematical model for algorithm-tree, from the unified model for algorithm-tree, we can conclude that computation complexity for serial processing NP problem if under parallel processing sometimes we can obtain P=NP  in time-complexity, but that will imply another NP, non-deterministic space-complexity NP, i.e., under serial processing P≠NP  in space-complexity, and the result is excluded the case of NP problem that there exists a faster algorithm to replace the brute-force algorithm, and hence we can proof that under parallel processing time-complexity is depended on space-complexity, and vice verse, within P vs. NP problem, this point is just the natural property of P vs. NP problem so that “P≠NP ”.

APA, Harvard, Vancouver, ISO, and other styles

4

Beame, Paul, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. "The Relative Complexity of NP Search Problems." Journal of Computer and System Sciences 57, no. 1 (August 1998): 3–19. http://dx.doi.org/10.1006/jcss.1998.1575.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

CALUDE, CRISTIAN S., ELENA CALUDE, and MELISSA S. QUEEN. "INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM." Parallel Processing Letters 23, no. 01 (March 2013): 1350007. http://dx.doi.org/10.1142/s0129626413500072.

Full text

Abstract:

This paper does not propose a solution, not even a new possible attack, to the P versus NP problem. We are asking the simpler question: How “complex” is the P versus NP problem? Using the inductive complexity measure—a measure based on computations run by inductive register machines of various orders—developed in [2], we determine an upper bound on the inductive complexity of second order of the P versus NP problem. From this point of view, the P versus NP problem is significantly more complex than the Riemann hypothesis. To date, the P versus NP problem and the Goostein theorem (which is unprovable in Peano Arithmetic) are the most complex mathematical statements (theorems, conjectures and problems) studied in this framework [9, 5, 6, 2, 20].

APA, Harvard, Vancouver, ISO, and other styles

6

Littman, M. L., J. Goldsmith, and M. Mundhenk. "The Computational Complexity of Probabilistic Planning." Journal of Artificial Intelligence Research 9 (August 1, 1998): 1–36. http://dx.doi.org/10.1613/jair.505.

Full text

Abstract:

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.

APA, Harvard, Vancouver, ISO, and other styles

7

Jukna, Stasys. "On the P versus NP intersected with co-NP question in communication complexity." Information Processing Letters 96, no. 6 (December 2005): 202–6. http://dx.doi.org/10.1016/j.ipl.2005.08.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Mulmuley, Ketan D. "On P vs. NP and geometric complexity theory." Journal of the ACM 58, no. 2 (April 2011): 1–26. http://dx.doi.org/10.1145/1944345.1944346.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Birget, J. C. "Inverse monoids associated with the complexity class NP." Semigroup Forum 98, no. 2 (January 3, 2019): 369–97. http://dx.doi.org/10.1007/s00233-018-9990-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Buss, Samuel R. "Towards NP–P via proof complexity and search." Annals of Pure and Applied Logic 163, no. 7 (July 2012): 906–17. http://dx.doi.org/10.1016/j.apal.2011.09.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Díez-Bedmar, María Belén, and Pascual Pérez-Paredes. "Noun phrase complexity in young Spanish EFL learners’ writing." International Journal of Corpus Linguistics 25, no. 1 (April 16, 2020): 4–35. http://dx.doi.org/10.1075/ijcl.17058.die.

Full text

Abstract:

Abstract The research reported in this article examines Noun Phrase (NP) syntactic complexity in the writing of Spanish EFL secondary school learners in Grades 7, 8, 11 and 12 in the International Corpus of Crosslinguistic Interlanguage. Two methods were combined: a manual parsing of NPs and an automatic analysis of NP indices using the Tool for the Automatic Analysis of Syntactic Sophistication and Complexity (TAASSC). Our results revealed that it is in premodifying slots that syntactic complexity in NPs develops. We argue that two measures, (i) nouns and modifiers (a syntactic complexity index) and (ii) determiner + multiple premodification + head (a NP type obtained as a result of a corpus-driven analysis), can be used as indices of syntactic complexity in young Spanish EFL learner language development. Besides offering a learner-language-driven taxonomy of NP syntactic complexity, the paper underscores the strength of using combined methods in SLA research.

APA, Harvard, Vancouver, ISO, and other styles

12

Ioannou, L. M. "Computational complexity of the quantum separability problem." Quantum Information and Computation 7, no. 4 (May 2007): 336–70. http://dx.doi.org/10.26421/qic7.4-5.

Full text

Abstract:

Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or \emph{separable}, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem \cite{DPS02,DPS04,qphCKMR06}; and the entanglement-witness search (via interior-point algorithms and global optimization) \cite{ITCE04,IT06}. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.

APA, Harvard, Vancouver, ISO, and other styles

13

Fu, Bin, and Hong-Zhou Li. "Closeness of NP-Hard Sets to Other Complexity Classes." SIAM Journal on Computing 23, no. 2 (April 1994): 255–60. http://dx.doi.org/10.1137/s0097539792225935.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Dieu, Phan Dinh, Le Cong Thanh, and Le Tuan Hoa. "Average polynomial time complexity of some NP-complete problems." Theoretical Computer Science 46 (1986): 219–37. http://dx.doi.org/10.1016/0304-3975(86)90031-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

BIRGET, JEAN-CAMILLE. "THE THOMPSON–HIGMAN MONOIDS Mk,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY." International Journal of Algebra and Computation 21, no. 01n02 (February 2011): 1–34. http://dx.doi.org/10.1142/s0218196711006066.

Full text

Abstract:

The Thompson–Higman groups Gk,i have a natural generalization to monoids, called Mk,i, and inverse monoids, called Invk,i. We study some structural features of Mk,i and Invk,i and investigate the computational complexity of related decision problems. The main interest of these monoids is their close connection with circuits and circuit complexity. The maximal subgroups of Mk,1 and Invk,1 are isomorphic to the groups Gk,j (1 ≤ j ≤ k - 1); so we rediscover all the Thompson–Higman groups within Mk,1. Deciding the Green relations [Formula: see text] and [Formula: see text] of Mk,1, when the inputs are words over a finite generating set of Mk,1, is in P. When a circuit-like generating set is used for Mk,1 then deciding [Formula: see text] is coDP-complete (where DP is the complexity class consisting of differences of sets in NP). The multiplier search problem for [Formula: see text] is xNPsearch-complete, whereas the multiplier search problems of [Formula: see text] and [Formula: see text] are not in xNPsearch unless NP = coNP. The class of search problems xNPsearch is introduced as a slight generalization of NPsearch. Deciding [Formula: see text] for Mk,1 when the inputs are words over a circuit-like generating set, is ⊕k-1• NP -complete; for any h ≥ 2, ⊕h•NP is a modular counting complexity class, whose verification problems are in NP. Related problems for partial circuits are the image size problem (which is # • NP-complete), and the image size modulo h problem (which is ⊕h•NP-complete). For Invk,1 over a circuit-like generating set, deciding [Formula: see text] is ⊕k-1P-complete. It is interesting that the little known complexity classes coDP and ⊕k-1•NP play a central role in Mk,1.

APA, Harvard, Vancouver, ISO, and other styles

16

Jonsson, Peter, Victor Lagerkvist, and Biman Roy. "Fine-Grained Time Complexity of Constraint Satisfaction Problems." ACM Transactions on Computation Theory 13, no. 1 (March 2021): 1–32. http://dx.doi.org/10.1145/3434387.

Full text

Abstract:

We study the constraint satisfaction problem (CSP) parameterized by a constraint language Γ (CSPΓ) and how the choice of Γ affects its worst-case time complexity. Under the exponential-time hypothesis (ETH), we rule out the existence of subexponential algorithms for finite-domain NP-complete CSPΓ problems. This extends to certain infinite-domain CSPs and structurally restricted problems. For CSPs with finite domain D and where all unary relations are available, we identify a relation S D such that the time complexity of the NP-complete problem CSP({ S D }) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP({ S D }) strictly decreases when |D| increases (unless the ETH is false) and provide stronger complexity results in the special case when |D|=3.

APA, Harvard, Vancouver, ISO, and other styles

17

Schilk, Marco, and Steffen Schaub. "Noun phrase complexity across varieties of English." English World-Wide 37, no. 1 (March 3, 2016): 58–85. http://dx.doi.org/10.1075/eww.37.1.03sch.

Full text

Abstract:

The noun phrase (NP) is at the heart of several studies investigating regional variation in varieties of English. While so far the bulk of research has focused on isolated structural features, the present study is a comparative analysis of NP complexity across varieties of English. NP complexity is compared across five regional varieties and four text categories, based on data from the International Corpus of English. The study adopts a multinomial regression approach, which takes into consideration the interaction of three potential predictors: syntactic function, text type, and variety. The results underline the need for text-type-sensitive studies and add to an understanding of syntactic contact phenomena in varieties of English. More specifically, we find marked differences in the predictive power of the variables and illustrate how focusing on the interaction of syntactic functions, text type and regional variety contributes to a systematic description of variation in the NP in world Englishes.

APA, Harvard, Vancouver, ISO, and other styles

18

Akinlotan, Mayowa, and Alex Housen. "Noun phrase complexity in Nigerian English." English Today 33, no. 3 (January 30, 2017): 31–38. http://dx.doi.org/10.1017/s0266078416000626.

Full text

Abstract:

Structural simplicity/complexity is an important variable with which New Englishes and native varieties are identified and conceptualised, but predicting such variation in complexity has received little attention in the literature. New Englishes, especially the outer circle varieties such as Nigerian or Indian English, differ in form and function from the inner circle varieties, such as British or American English, but the extent of such variation varies greatly and merits further investigation. According to Gorlach (1998), we should expect New Englishes to demonstrate simplification at the levels of morphology, lexis, and syntax. This has indeed been shown to be the case in some varieties, but it has also been shown that this variation differs according to different linguistic and non-linguistic factors. Most recently, Schilk and Schaub (2016) have shown how noun phrase (NP) structure can reveal the underlying structural simpification predicted in the New Englishes varieties. Brunner (2014) examined NP complexity across three New Englishes (British, Singaporean, and Kenyan English), explicating how grammars of the indigeneous languages in Singapore and Kenya influence NP simplicity/complexity.

APA, Harvard, Vancouver, ISO, and other styles

19

Mandal, C. A., P. P. Chakrabarti, and S. Ghose. "Complexity of Scheduling in High Level Synthesis." VLSI Design 7, no. 4 (January 1, 1998): 337–46. http://dx.doi.org/10.1155/1998/52807.

Full text

Abstract:

This work examines the complexity of scheduling for high level synthesis. It has been shown that the problem of finding the minimum time schedule for a set of chains of operations of two types using two processors, one of each type, is NP-complete. However, for two chains only, a polynomial time algorithm can been obtained for scheduling with two processors. The problem of scheduling a rooted binary tree of two operation types on two processors, one of each type, has been shown to be NP-complete. It has also been proved that absolute approximations for schedule length minimization or processor minimization are NP-complete. A related resource constrained scheduling problem has also been shown to be NP-hard.

APA, Harvard, Vancouver, ISO, and other styles

20

Meier, Arne. "Incremental FPT Delay." Algorithms 13, no. 5 (May 15, 2020): 122. http://dx.doi.org/10.3390/a13050122.

Full text

Abstract:

In this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt-time in terms of exponent slices and show how they interleave. Furthermore, we define several parameterized function classes and, in particular, introduce the parameterized counterpart of the class of nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist, TFNP, known from Megiddo and Papadimitriou (TCS 1991). We show that this class TF(para-NP), the restriction of the function variant of NP to total functions, collapsing to F(FPT), the function variant of FPT, is equivalent to the result that OutputFPT coincides with IncFPT. In addition, these collapses are shown to be equivalent to TFNP = FP, and also equivalent to P equals NP intersected with coNP. Finally, we show that these two collapses are equivalent to the collapse of IncP and OutputP in the classical setting. These results are the first direct connections of collapses in parameterized enumeration complexity to collapses in classical enumeration complexity, parameterized function complexity, classical function complexity, and computational complexity theory.

APA, Harvard, Vancouver, ISO, and other styles

21

De Haan, Ronald, Iyad Kanj, and Stefan Szeider. "On the Subexponential-Time Complexity of CSP." Journal of Artificial Intelligence Research 52 (January 30, 2015): 203–34. http://dx.doi.org/10.1613/jair.4540.

Full text

Abstract:

Not all NP-complete problems share the same practical hardness with respect to exact computation. Whereas some NP-complete problems are amenable to efficient computational methods, others are yet to show any such sign. It becomes a major challenge to develop a theoretical framework that is more fine-grained than the theory of NP-completeness, and that can explain the distinction between the exact complexities of various NP-complete problems. This distinction is highly relevant for constraint satisfaction problems under natural restrictions, where various shades of hardness can be observed in practice. Acknowledging the NP-hardness of such problems, one has to look beyond polynomial time computation. The theory of subexponential-time complexity provides such a framework, and has been enjoying increasing popularity in complexity theory. An instance of the constraint satisfaction problem with n variables over a domain of d values can be solved by brute-force in dn steps (omitting a polynomial factor). In this paper we study the existence of subexponential-time algorithms, that is, algorithms running in do(n) steps, for various natural restrictions of the constraint satisfaction problem. We consider both the constraint satisfaction problem in which all the constraints are given extensionally as tables, and that in which all the constraints are given intensionally in the form of global constraints. We provide tight characterizations of the subexponential-time complexity of the aforementioned problems with respect to several natural structural parameters, which allows us to draw a detailed landscape of the subexponential-time complexity of the constraint satisfaction problem. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem.

APA, Harvard, Vancouver, ISO, and other styles

22

Annila, Arto. "Physical Portrayal of Computational Complexity." ISRN Computational Mathematics 2012 (March 5, 2012): 1–15. http://dx.doi.org/10.5402/2012/321372.

Full text

Abstract:

Computational complexity is examined using the principle of increasing entropy. To consider computation as a physical process from an initial instance to the final acceptance is motivated because information requires physical representations and because many natural processes complete in nondeterministic polynomial time (NP). The irreversible process with three or more degrees of freedom is found intractable when, in terms of physics, flows of energy are inseparable from their driving forces. In computational terms, when solving a problem in the class NP, decisions among alternatives will affect subsequently available sets of decisions. Thus the state space of a nondeterministic finite automaton is evolving due to the computation itself, hence it cannot be efficiently contracted using a deterministic finite automaton. Conversely when solving problems in the class P, the set of states does not depend on computational history, hence it can be efficiently contracted to the accepting state by a deterministic sequence of dissipative transformations. Thus it is concluded that the state set of class P is inherently smaller than the state set of class NP. Since the computational time needed to contract a given set is proportional to dissipation, the computational complexity class P is a proper (strict) subset of NP.

APA, Harvard, Vancouver, ISO, and other styles

23

Ko, Ker-I., and Uwe Schöning. "On Circuit-Size Complexity and the Low Hierarchy in NP." SIAM Journal on Computing 14, no. 1 (February 1985): 41–51. http://dx.doi.org/10.1137/0214003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

CHEN, ZHI-ZHONG, and SEINOSUKE TODA. "ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS." International Journal of Foundations of Computer Science 02, no. 03 (September 1991): 207–20. http://dx.doi.org/10.1142/s0129054191000133.

Full text

Abstract:

We study the computational complexity of computing optimal solutions (the solutions themselves, not just their cost) for NP optimization problems where the costs of feasible solutions are bounded above by a polynomial in the length of their instances (we simply denote by NPOP such an NP optimization problem). It is of particular interest to find a computational structure (or equivalently, a complexity class) which. captures that complexity, if we consider the problems of computing optimal solutions for NPOP’s as a class of functions giving those optimal solutions. In this paper, we will observe that [Formula: see text] the class of functions computable in polynomial-time with one free evaluation of unbounded parallel queries to NP oracle sets, captures that complexity. We first show that for any NPOP Π, there exists a polynomial-time bounded randomized algorithm which, given an instance of Π, uses one free evaluation of parallel queries to an NP oracle set and outputs some optimal solution of the instance with very high probability. We then show that for several natural NPOP’s, any function giving those optimal solutions is at least as computationally hard as all functions in [Formula: see text]. To show the hardness results, we introduce a property of NPOP’s, called paddability, and we show a general result that if Π is a paddable NPOP and its associated decision problem is NP-hard, then all functions in [Formula: see text] are computable in polynomial-time with one free evaluation of an arbitrary function giving optimal solutions for instances of Π. The hardness results are applications of this general result. Among the NPOP’s, we include MAXIMUM CLIQUE, MINIMUM COLORING, LONGEST PATH, LONGEST CYCLE, 0–1 TRAVELING SALESPERSON, and 0–1 INTEGER PROGRAMMING.

APA, Harvard, Vancouver, ISO, and other styles

25

BERGMAN, CLIFFORD, and GIORA SLUTZKI. "COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA." International Journal of Algebra and Computation 12, no. 05 (October 2002): 719–35. http://dx.doi.org/10.1142/s0218196702001127.

Full text

Abstract:

We discuss the computational complexity of several problems concerning subsets of an algebraic structure that generate the structure. We show that the problem of determining whether a given subset X generates an algebra A is P-complete, while determining the size of the smallest generating set is NP-complete. We also consider several questions related to the Frattini subuniverse, Φ(A), of an algebra A. We show that the membership problem for Φ(A) is co-NP-complete, while the membership problems for Φ(Φ(A)), Φ(Φ(Φ(A))),… all lie in the class P‖(NP).

APA, Harvard, Vancouver, ISO, and other styles

26

Cook, Stephen, and Jan Krajíček. "Consequences of the provability of NP ⊆ P/poly." Journal of Symbolic Logic 72, no. 4 (December 2007): 1353–71. http://dx.doi.org/10.2178/jsl/1203350791.

Full text

Abstract:

AbstractWe prove the following results: (i) PV proves NP ⊆ P/poly iff PV proves coNP ⊆ NP/O(1). (ii) If PV proves NP ⊆ P/poly then PV proves that the Polynomial Hierarchy collapses to the Boolean Hierarchy, (iii) proves NP ⊆ P/poly iff proves coNP ⊆ NP/O(log n). (iv) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP[log n]. (v) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP.Motivated by these results we introduce a new concept in proof complexity: proof systems with advice, and we make some initial observations about them.

APA, Harvard, Vancouver, ISO, and other styles

27

Bonatti, P. A., C. Lutz, and F. Wolter. "The Complexity of Circumscription in DLs." Journal of Artificial Intelligence Research 35 (August 26, 2009): 717–73. http://dx.doi.org/10.1613/jair.2763.

Full text

Abstract:

As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.

APA, Harvard, Vancouver, ISO, and other styles

28

HEMASPAANDRA, LANE A., ALBRECHT HOENE, ASHISH V. NAIK, MITSUNORI OGIHARA, ALAN L. SELMAN, THOMAS THIERAUF, and JIE WANG. "NONDETERMINISTICALLY SELECTIVE SETS." International Journal of Foundations of Computer Science 06, no. 04 (December 1995): 403–16. http://dx.doi.org/10.1142/s0129054195000214.

Full text

Abstract:

In this note, we study NP-selective sets (formally, sets that are selective via NPSV t functions) as a natural generalization of P-selective sets. We show that, assuming P≠NP∩coNP , the class of NP-selective sets properly contains the class of P-selective sets. We study several properties of NP-selective sets such as self-reducibility, hardness under various reductions, lowness, and nonuniform complexity. We prove many of our results via a “relativization technique,” by using the known properties of P-selective sets. Using this technique, we strengthen a result of Longpré and Selman on hard promise problems and show that the result “ NP ⊆( NP ∩ coNP )/ poly ⇒ PH=NP NP ” is implicit in Karp and Lipton’s seminal result on nonuniform classes.

APA, Harvard, Vancouver, ISO, and other styles

29

Ilyas, Tahir. "Quantum Limits, Computational Complexity and Philosophy – A Review." Lahore Garrison University Research Journal of Computer Science and Information Technology 2, no. 1 (April 22, 2020): 9–20. http://dx.doi.org/10.54692/lgurjcsit.2018.020139.

Full text

Abstract:

Quantum computing physics uses quantum qubits (or bits), for computer’s memory or processor. They can perform certain calculations much faster than a normal computer. The quantum computers have some limitations due to which the problems belonging to NP- Complete are not solved efficiently. This paper covers effective quantum algorithm for solving NP-Complete problems through some features of complexity theory, that we can simplify some of the philosophical interest problems.

APA, Harvard, Vancouver, ISO, and other styles

30

Hitchcock, John M., Adewale Sekoni, and Hadi Shafei. "Polynomial-Time Random Oracles and Separating Complexity Classes." ACM Transactions on Computation Theory 13, no. 1 (March 2021): 11–16. http://dx.doi.org/10.1145/3434389.

Full text

Abstract:

Bennett and Gill [1981] showed that P A ≠ NP A ≠ coNP A for a random oracle A , with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the sense of martingales and resource-bounded measure [Lutz 1992; Ambos-Spies et al. 1997], and p-betting-game random oracles using the betting games generalization of resource-bounded measure [Buhrman et al. 2000]. Every p-betting-game random oracle is also p-random; whether the two notions are equivalent is an open problem. (1) We first show that P A ≠ NP A for every oracle A that is p-betting-game random. Ideally, we would extend (1) to p-random oracles. We show that answering this either way would imply an unrelativized complexity class separation: (2) If P A ≠ NP A relative to every p-random oracle A , then BPP ≠ EXP. (3) If P A ≠ NP A relative to some p-random oracle A , then P ≠ PSPACE. Rossman, Servedio, and Tan [2015] showed that the polynomial-time hierarchy is infinite relative to a random oracle, solving a longstanding open problem. We consider whether we can extend (1) to show that PH A is infinite relative to oracles A that are p-betting-game random. Showing that PH A separates at even its first level would also imply an unrelativized complexity class separation: (4) If NP A ≠ coNP A for a p-betting-game measure 1 class of oracles A , then NP ≠ EXP. (5) If PH A is infinite relative to every p-random oracle A , then PH ≠ EXP. We also consider random oracles for time versus space, for example: (6) L A ≠ P A relative to every oracle A that is p-betting-game random.

APA, Harvard, Vancouver, ISO, and other styles

31

Kreyer, Rolf, and Steffen Schaub. "The development of phrasal complexity in German intermediate learners of English." International Journal of Learner Corpus Research 4, no. 1 (May 31, 2018): 82–111. http://dx.doi.org/10.1075/ijlcr.16011.kre.

Full text

Abstract:

Abstract On the basis of a longitudinal corpus of English produced by German intermediate learners, the present paper explores how noun phrase (NP) complexity develops in terms of global measures of complexity (length, number of modifiers per 1,000 words) in learner data on an intermediate level of competence and describes how the use of individual NP-modification structures changes as learners progress through their three final years of secondary school. An additional objective is to test Biber et al.’s (2011) hypothesized stages of acquisition against our data of intermediate learner English, complementing the data of advanced learner English provided by Parkinson & Musgrave (2014). Our results show that global measures of NP complexity remain stable as learners progress from grades 10 to 12. Zooming in on individual learners and features, the results lend tentative support to Biber et al.’s (2011) stages of acquisition. However, individual variation influences the frequency of noun-phrasal modifiers.

APA, Harvard, Vancouver, ISO, and other styles

32

Adelson-Velsky, George M., Alexander Gelbukh, and Eugene Levner. "On fast path-finding algorithms in AND-OR graphs." Mathematical Problems in Engineering 8, no. 4-5 (2002): 283–93. http://dx.doi.org/10.1080/10241230306728.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Hartarsky, Ivailo, and Tamás Róbert Mezei. "Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness." SIAM Journal on Discrete Mathematics 34, no. 2 (January 2020): 1444–59. http://dx.doi.org/10.1137/19m1239933.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Chen, Jian-Er. "Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardness." Journal of Computer Science and Technology 20, no. 1 (January 2005): 18–37. http://dx.doi.org/10.1007/s11390-005-0003-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Tunçel, Levent. "Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard." Mathematical Programming 86, no. 1 (September 1, 1999): 219–23. http://dx.doi.org/10.1007/s101070050087.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Sanchis, Laura A. "On the complexity of test case generation for NP-hard problems." Information Processing Letters 36, no. 3 (November 1990): 135–40. http://dx.doi.org/10.1016/0020-0190(90)90082-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Kharlampovich, Olga, and Alina Vdovina. "Low complexity algorithms in knot theory." International Journal of Algebra and Computation 29, no. 02 (March 2019): 245–62. http://dx.doi.org/10.1142/s0218196718500698.

Full text

Abstract:

Agol, Haas and Thurston showed that the problem of determining a bound on the genus of a knot in a 3-manifold, is NP-complete. This shows that (unless P[Formula: see text]NP) the genus problem has high computational complexity even for knots in a 3-manifold. We initiate the study of classes of knots where the genus problem and even the equivalence problem have very low computational complexity. We show that the genus problem for alternating knots with n crossings has linear time complexity and is in Logspace[Formula: see text]. Alternating knots with some additional combinatorial structure will be referred to as standard. As expected, almost all alternating knots of a given genus are standard. We show that the genus problem for these knots belongs to [Formula: see text] circuit complexity class. We also show, that the equivalence problem for such knots with [Formula: see text] crossings has time complexity [Formula: see text] and is in Logspace[Formula: see text] and [Formula: see text] complexity classes.

APA, Harvard, Vancouver, ISO, and other styles

38

Bäckström, C., and P. Jonsson. "A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond." Journal of Artificial Intelligence Research 47 (July 30, 2013): 575–611. http://dx.doi.org/10.1613/jair.3968.

Full text

Abstract:

The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.

APA, Harvard, Vancouver, ISO, and other styles

39

Seki, Shinnosuke, and Andrew Winslow. "The Complexity of Fixed-Height Patterned Tile Self-Assembly." International Journal of Foundations of Computer Science 28, no. 05 (August 2017): 465–82. http://dx.doi.org/10.1142/s0129054117400020.

Full text

Abstract:

We characterize the complexity of the PATS problem for patterns of fixed height and color count in variants of the model where seed glues are either chosen or fixed and identical (so-called non-uniform and uniform variants). We prove that both variants are NP-complete for patterns of height 2 or more and admit [Formula: see text]-time algorithms for patterns of height 1. We also prove that if the height and number of colors in the pattern is fixed, the non-uniform variant admits a [Formula: see text]-time algorithm while the uniform variant remains NP-complete. The NP-completeness results use a new reduction from a constrained version of a problem on finite state transducers.

APA, Harvard, Vancouver, ISO, and other styles

40

DURRLEMAN, STEPHANIE, THEODOROS MARINIS, and JULIE FRANCK. "Syntactic complexity in the comprehension of wh-questions and relative clauses in typical language development and autism." Applied Psycholinguistics 37, no. 6 (March 29, 2016): 1501–27. http://dx.doi.org/10.1017/s0142716416000059.

Full text

Abstract:

ABSTRACTThis study investigates effects of syntactic complexity operationalized in terms of movement, intervention, and noun phrase (NP) feature similarity in the development of Aʹ-dependencies in 4-, 6-, and 8-year-old typically developing (TD) French children and children with autism spectrum disorder. Children completed an offline comprehension task testing eight syntactic structures classified in four levels of complexity: Level 0: no movement; Level 1: movement without (configurational) intervention; Level 2: movement with intervention from an element that is maximally different or featurally “disjoint” (mismatched in both lexical NP restriction and number); and Level 3: movement with intervention from an element similar in one feature or featurally “intersecting” (matched in lexical NP restriction, mismatched in number). The results show that syntactic complexity affects TD children across the three age groups, but also indicate developmental differences between these groups. Movement affected all three groups in a similar way, but intervention effects in intersection cases were stronger in younger than in older children, with NP feature similarity affecting only 4-year-olds. Complexity effects created by the similarity in lexical restriction of an intervener thus appear to be overcome early in development, arguably thanks to other differences of this intervener (which was mismatched in number). Children with autism spectrum disorder performed less well than the TD children although they were matched on nonverbal reasoning. Overall, syntactic complexity affected their performance in a similar way as in their TD controls, but their performance correlated with nonverbal abilities rather than age, suggesting that their grammatical development does not follow the smooth relation to age that is found in TD children.

APA, Harvard, Vancouver, ISO, and other styles

41

Valencia-Cabrera, Luis, David Orellana-Martín, Miguel Á. Martínez-del-Amor, Ignacio Pérez-Hurtado, and Mario J. Pérez-Jiménez. "From NP-Completeness to DP-Completeness: A Membrane Computing Perspective." Complexity 2020 (August 30, 2020): 1–10. http://dx.doi.org/10.1155/2020/6765097.

Full text

Abstract:

Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ is closed under complement and under polynomial-time reduction. Therefore, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ. In this paper, the lower bound NP ∪ co-NP for the time complexity class PMCℛ is improved for any presumably efficient computing model ℛ of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that DP ∪ co-DP is a lower bound for such PMCℛ, where DP is the class of differences of any two languages in NP. Since NP ∪ co-NP ⊆ DP ∩ co-DP, this lower bound for PMCℛ delimits a thinner frontier than that with NP ∪ co-NP.

APA, Harvard, Vancouver, ISO, and other styles

42

Chia, Nai-Hui, Sean Hallgren, and Fang Song. "On Basing One-way Permutations on NP-hard Problems under Quantum Reductions." Quantum 4 (August 27, 2020): 312. http://dx.doi.org/10.22331/q-2020-08-27-312.

Full text

Abstract:

A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP⊆QIP(2).

APA, Harvard, Vancouver, ISO, and other styles

43

Morgan, Perri, Christine M. Everett, Valerie A. Smith, Sandra Woolson, David Edelman, Cristina C. Hendrix, Theodore S. Z. Berkowitz, Brandolyn White, and George L. Jackson. "Factors Associated With Having a Physician, Nurse Practitioner, or Physician Assistant as Primary Care Provider for Veterans With Diabetes Mellitus." INQUIRY: The Journal of Health Care Organization, Provision, and Financing 54 (January 1, 2017): 004695801771276. http://dx.doi.org/10.1177/0046958017712762.

Full text

Abstract:

Expanded use of nurse practitioners (NPs) and physician assistants (PAs) is a potential solution to workforce issues, but little is known about how NPs and PAs can best be used. Our study examines whether medical and social complexity of patients is associated with whether their primary care provider (PCP) type is a physician, NP, or PA. In this national retrospective cohort study, we use 2012-2013 national Veterans Administration (VA) electronic health record data from 374 223 veterans to examine whether PCP type is associated with patient, clinic, and state-level factors representing medical and social complexity, adjusting for all variables simultaneously using a generalized logit model. Results indicate that patients with physician PCPs are modestly more medically complex than those with NP or PA PCPs. For the group having a Diagnostic Cost Group (DCG) score >2.0 compared with the group having DCG <0.5, odds of having an NP or a PA were lower than for having a physician PCP (NP odds ratio [OR] = 0.83, 95% confidence interval [CI]: 0.79-0.88; PA OR = 0.85, CI: 0.80-0.89). Social complexity is not consistently associated with PCP type. Overall, we found minor differences in provider type assignment. This study improves on previous work by using a large national dataset that accurately ascribes the work of NPs and PAs, analyzing at the patient level, analyzing NPs and PAs separately, and addressing social as well as medical complexity. This is a requisite step toward studies that compare patient outcomes by provider type.

APA, Harvard, Vancouver, ISO, and other styles

44

Stewart, Iain A. "Logical Characterizations of Bounded Query Classes I: Logspace Oracle Machines." Fundamenta Informaticae 18, no. 1 (January 1, 1993): 65–92. http://dx.doi.org/10.3233/fi-1993-18105.

Full text

Abstract:

We consider three sub-logics of the logic (±HP)*[FOs] and show that these sub-logics capture the complexity classes obtained by considering logspace deterministic oracle Turing machines with oracles in NP where the number of oracle calls is unrestricted and constant, respectively; that is, the classes LNP and LNP[O(1)]. We conclude that if certain logics are of the same expressibility then the Polynomial Hierarchy collapses. We also exhibit some new complete problems for the complexity class LNP via projection translations (the first to be discovered: projection translations are extremely weak logical reductions between problems) and characterize the complexity class LNP[O(1)] as the closure of NP under a new, extremely strict truth-table reduction (which we introduce in this paper).

APA, Harvard, Vancouver, ISO, and other styles

45

Procaccia, A. D., and J. S. Rosenschein. "Junta Distributions and the Average-Case Complexity of Manipulating Elections." Journal of Artificial Intelligence Research 28 (February 28, 2007): 157–81. http://dx.doi.org/10.1613/jair.2148.

Full text

Abstract:

Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation. Indeed, we demonstrate that NP-hard manipulations may be tractable in the average case. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant.

APA, Harvard, Vancouver, ISO, and other styles

46

BRUNNER, THOMAS. "Structural nativization, typology and complexity: noun phrase structures in British, Kenyan and Singaporean English." English Language and Linguistics 18, no. 1 (February 6, 2014): 23–48. http://dx.doi.org/10.1017/s1360674313000269.

Full text

Abstract:

Two much-cited explanations for linguistic innovations in varieties of New Englishes are cross-linguistic influence (see Gut 2011) and simplification (see Schneider 2007: 82). Using these two notions as starting points, the present study seeks to detect effects of structural nativization in noun phrase (NP) modification in two varieties of English whose substrate languages differ strongly from a typological point of view: Singaporean and Kenyan English. The results yielded by the comparison of random samples extracted from the relevant components of the International Corpus of English in the first part of the study show striking correspondences between the preferred NP structures in the varieties at hand and NP structures in the local languages concerned, which, in the light of Mufwene's (2001, 2008) ecological theory of language change, can be interpreted as effects of language contact. The second part of the study shows that the NPs from the three varieties also differ in terms of variables which can be viewed as measures of NP complexity. What is more, the different degrees of complexity found in the samples correspond closely to predictions about the evolutionary status of the varieties at hand made by Schneider's (2007) Dynamic Model.

APA, Harvard, Vancouver, ISO, and other styles

47

Leung, Joseph Y. T., and Burkhard Monien. "On the Complexity of Deadlock Recovery." Fundamenta Informaticae 9, no. 3 (July 1, 1986): 323–42. http://dx.doi.org/10.3233/fi-1986-9304.

Full text

Abstract:

We consider the computational complexity of finding an optimal deadlock recovery. It is known that for an arbitrary number of resource types the problem is NP-hard even when the total cost of deadlocked jobs and the total number of resource units are “small” relative to the number of deadlocked jobs. It is also known that for one resource type the problem is NP-hard when the total cost of deadlocked jobs and the total number of resource units are “large” relative to the number of deadlocked jobs. In this paper we show that for one resource type the problem is solvable in polynomial time when the total cost of deadlocked jobs or the total number of resource units is “small” relative to the number of deadlocked jobs. For fixed m ⩾ 2 resource types, we show that the problem is solvable in polynomial time when the total number of resource units is “small” relative to the number of deadlocked jobs. On the other hand, when the total number of resource units is “large”, the problem becomes NP-hard even when the total cost of deadlocked jobs is “small” relative to the number of deadlocked jobs. The results in the paper, together with previous known ones, give a complete delineation of the complexity of this problem under various assumptions of the input parameters.

APA, Harvard, Vancouver, ISO, and other styles

48

Akinlotan, Mayowa. "Noun phrase complement in Nigerian English." BELT - Brazilian English Language Teaching Journal 9, no. 2 (January 15, 2019): 342. http://dx.doi.org/10.15448/2178-3640.2018.2.31724.

Full text

Abstract:

The present study investigates the structure of of-complement noun phrase in Nigerian English, comparing findings with those of British and Ghanaian varieties. Of-complement is high in frequency and is a typical complement that has structural tendencies for recursiveness and complexity. A review of literature explicating the structural simplification hypothesis (Gorlach, 1998) suggests that the structure of-complement (or any other type) has received very little attention. Perhaps such scanty works show the different arguments surrounding its syntactic and theoretical status in different grammatical descriptions. Unlike many previous NP frameworks, Huddleston & Pullum (2002, 2004) argued that complements are not only a syntactic element within the NP structure, but also that they are of equal obligatory syntactic status as a head noun within an NP. This framework, unlike many others, therefore conceptualizes the complement slot as an important part in the scheme of things for an NP structure viz-a-viz its complexity. Thus, a serious examination of NP complexity would consider the cooperation (relationship) between a complement and the other syntactic elements constituting the NP structure. This is one of many issues that the present study sheds light on. On the basis of variables representing syntactic function and text type, together with corpus analyses of NPs extracted from the Nigerian component of International Corpus of English (ICE), the structural behavior of of-complement in the lights of other internal elements constituting an NP structure, is clearly shown. It is found that a complement is less likely to co-occur with other all internal elements (20%). Also, it is shown that an of-complement is likely to co-occur with prenominal elements (30%). Furthermore, the paper shows that a structural type of of-complement representing h-complement (i.e. an NP structure consisting of a head noun + a complement, see Huddleston & Pullum, 2002, 2004, and Akinlotan & Housen, 2017) is more likely to occur (26%) as an independent NP structure than to co-occur with postnominal elements (24%). The structural simplification hypothesis is manifested in our corpus data, as it is found out that a complement is more likely to be simple-structured (54%) than complex-structured (46%). On the predictive strength of syntactic function and text type (Biber et al., 1999; Schilk & Schuab, 2016; Akinlotan, 2017), the study finds syntactic function a better predictor than text type.

APA, Harvard, Vancouver, ISO, and other styles

49

Liu, J. F., and K. A. Abdel-Malek. "On the Problem of Scheduling Parallel Computations of Multibody Dynamic Analysis." Journal of Dynamic Systems, Measurement, and Control 121, no. 3 (September 1, 1999): 370–76. http://dx.doi.org/10.1115/1.2802484.

Full text

Abstract:

A formulation of a graph problem for scheduling parallel computations of multibody dynamic analysis is presented. The complexity of scheduling parallel computations for a multibody dynamic analysis is studied. The problem of finding a shortest critical branch spanning tree is described and transformed to a minimum radius spanning tree, which is solved by an algorithm of polynomial complexity. The problems of shortest critical branch minimum weight spanning tree (SCBMWST) and the minimum weight shortest critical branch spanning tree (MWSCBST) are also presented. Both problems are shown to be NP-hard by proving that the bounded critical branch bounded weight spanning tree (BCBBWST) problem is NP-complete. It is also shown that the minimum computational cost spanning tree (MCCST) is at least as hard as SCBMWST or MWSCBST problems, hence itself an NP-hard problem. A heuristic approach to solving these problems is developed and implemented, and simulation results are discussed.

APA, Harvard, Vancouver, ISO, and other styles

50

LIN, YAW-LING, and STEVEN S. SKIENA. "COMPLEXITY ASPECTS OF VISIBILITY GRAPHS." International Journal of Computational Geometry & Applications 05, no. 03 (September 1995): 289–312. http://dx.doi.org/10.1142/s0218195995000179.

Full text

Abstract:

In this paper, we consider two distinct problems related to complexity aspects of the visibility graphs of simple polygons. Recognizing visibility graphs is a long-standing open problem. It is not even known whether visibility graph recognition is in NP. That visibility graph recognition is in NP would be established if we could demonstrate that any n vertex visibility graph is realized by a polygon which can be drawn on an exponentially-sized grid. This motivates a study of the area requirements for realizing visibility graphs. In this paper, we prove: • Θ(n3) area is necessary and sufficient to realize the complete visibility graph Kn. • There exist visibility graphs which require exponential area to realize. • Any maximal outerplanar graph of diameter d can be realized in O(d2 · 2d) area, which can be as small as O(n log2 n) for a balanced mop. Linear maximal outer-planar graphs can be realized in O(n8) area. The second part of this paper considers the complexity of specific optimization problems on visibility graphs. Given a polygon P, we show that finding a maximum independent set, minimum vertex cover, or maximum dominating set in the visibility graph of P are all NP-complete. Further we show that for polygons P1 and P2, the problem of testing if they have isomorphic visibility graphs is isomorphism-complete. These problems remain hard when given the visibility graphs as input.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'NP-complexity'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles