✦ LIBER ✦

Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

✍ Scribed by Stephen R. Mahaney

Publisher: Elsevier Science
Year: 1982
Tongue: English
Weight: 942 KB
Volume: 25
Category: Article
ISSN: 0022-0000
DOI: 10.1016/0022-0000(82)90002-2

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Sparse Hard Sets for P: Resolution of a

Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis

✍ Jin-Yi Cai; D. Sivakumar 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 170 KB

Building on a recent breakthrough by Ogihara, we resolve a conjecture made by Hartmanis in 1978 regarding the (non)existence of sparse sets complete for P under logspace many one reductions. We show that if there exists a sparse hard set for P under logspace many one reductions, then P=LOGSPACE. We

The NP-completeness of steiner tree and

The NP-completeness of steiner tree and dominating set for chordal bipartite graphs

✍ Haiko Müller; Andreas Brandstädt 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 838 KB

A counter-example to a conjecture relati

A counter-example to a conjecture relating complete sets of frequency squares and affine geometries

✍ C. Laywine 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 459 KB

By generalizing the construction of complete sets of mutually orthogonal latin squares from affine planes, showed how to obtain complete sets of mutually orthogonal frequency squares from affine geometries. In this paper, the construction of a complete set of frequency squares not equivalent to an

Exact solutions for a complete set of LC

Exact solutions for a complete set of LC transformer-like bandpass matching circuits

✍ Abelardo Podcameni 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB

The task of matching real and complex loads, for applications in the RF, microwa¨e, and optoelectronic areas, is addressed here. Four three-element true-bandpass LC networks, forming a family capable of matching any kind of real and first-order reacti¨ely constrained loads, are presented and discuss

Iterative approximation of solutions for

Iterative approximation of solutions for a class of completely generalized set-valued quasi-variational inclusions

✍ Lu-Chuan Ceng; Sy-Ming Guu; Jen-Chih Yao 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 253 KB

In this paper we study a new class of completely generalized set-valued quasi-variational inclusion problems in Banach spaces. This inclusion problem is a generalization of the generalized set-valued variational inclusion problem studied by Chang et al. We show that Chang et al.'s algorithm can be m

The Solution of a Conjecture of Stanley

The Solution of a Conjecture of Stanley and Wilf for All Layered Patterns

✍ Miklós Bóna 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 101 KB

Proving a conjecture of Wilf and Stanley in hitherto the most general case, we show that for any layered pattern q there is a constant c so that q is avoided by less than c n permutations of length n. This will imply the solution of this conjecture for at least 2 k patterns of length k, for any k.