The polynomial-exponent AND-weakness conjecture for finite solvable groups
Statement
Let be a finite solvable group. An -input -program is a sequence of group elements selected according to the values of input bits, and it computes the -input function when membership in some subset of agrees with the function's value. Polynomial-exponent AND-weakness conjecture. Every -program for the -input function has length
This is proposed as a possible weaker form of the AND-weakness conjecture after the paper explains that stronger and certain refined forms are false or unsupported; its resolution is left open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.