Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Detecting monomials with k distinct variables

In English

Författare

Summary, in English

We study the complexity of detecting monomials with special properties in the sum-product expansion of a polynomial represented by an arithmetic circuit of size polynomial in the number of input variables and using only multiplication and addition. We focus on monomial properties expressed in terms of the number of distinct variables occurring in a monomial. Our first result is a randomized FPT algorithm for detection of a monomial having at least k distinct variables, parametrized with respect to k. For a more restricted class of circuits, we can also provide a deterministic FPT algorithm for detection of a monomial having at most k distinct variables parametrized by the degree of the polynomial represented by the input circuit. Furthermore, we derive several hardness results on detection of monomials with such properties within exact, parametrized and approximation complexity. In particular, we observe that the detection of a monomial having at most k distinct variables is W[2]-hard for the parameter k. (C) 2014 Elsevier B.V. All rights reserved.

Avdelning/ar

Publiceringsår

2015

Språk

Engelska

Sidor

82-86

Publikation/Tidskrift/Serie

Information Processing Letters

Volym

115

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

Elsevier

Ämne

  • Mathematics
  • Computer Science

Nyckelord

  • Algorithms
  • Polynomial
  • Monomial
  • Arithmetic circuit
  • Parametrized
  • complexity
  • Approximation hardness

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0020-0190