# Tag Info

Accepted

### How "hard" is it to maximize a polynomial function subject to linear constraints?

Your problem is NP-hard, even for polynomials of degree 2. The crucial reference is Theodore Motzkin and Ernst Strauss (1965) "Maxima for graphs and a new proof of a theorem of Turan" ...
• 5,772
Accepted

### Algebraic equivalent of SAT?

This is standard and widely used in computer science theory. There are many references that use boolean polynomials with False -> 0 and True -> 1, or in other words, a polynomial over GF(2) used ...
• 12.2k

### Algebraic equivalent of SAT?

I think what you are asking about is also known as "polynomial calculus" in proof complexity and SAT solving. It was introduced in [1, 2] to investigate whether coNP can be separated from NP ...
• 11.5k
Accepted

### a polynomial representation of boolean functions

Well done on your independent discovery. This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, ...
• 2,070
Accepted

### Finding a positive point for a collection of polynomials

Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY. THREE-SATISFIABILITY: Instance: Boolean variables $u_1,\ldots,u_n$; clauses $c_1,\ldots,c_m$ of length three over the $u_i$ ...
• 5,772
Accepted

### Maintaining the value of a polynomial over a dynamically updated input

Your idea generalizes as follows: given an algebraic circuit (over the finite field) or Boolean circuit (computing the bit-wise representation of your finite field elements) computing $P$, then ...
• 37.4k

### Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

It's easy, and in fact I suspect your proof that the "degree-3 version is NP-hard" is flawed somewhere, since the degree-3 version is also easy. Here's the argument for degree-2: Suppose our ...
• 1,429
Accepted

• 37.4k
Accepted

### Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy

If the coefficients are roots of rational numbers, then they are in particular algebraic numbers. This means that you can encode the coefficients as additional polynomial constraints. So overall, you'...
• 5,656
Accepted

• 958

### Applications of association schemes to complexity theory and other TCS

Coherent configurations are a close generalization of association schemes they have been used in Graph Isomorphism and Matrix Multiplication. (See e.g. this blog post of Peter Cameron that discusses ...
• 37.4k