Timeline for Is there an efficient algorithm for expression equivalence?
Current License: CC BY-SA 3.0
61 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 13, 2018 at 9:12 | answer | added | hyperpallium | timeline score: 0 | |
| Nov 27, 2014 at 19:08 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 27 characters in body
|
| Nov 19, 2014 at 5:46 | history | edited | hyperpallium | CC BY-SA 3.0 |
edited title
|
| Nov 19, 2014 at 5:39 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 120 characters in body
|
| Nov 19, 2014 at 5:28 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 120 characters in body
|
| Nov 19, 2014 at 2:45 | comment | added | hyperpallium | @RickyDemer yes, the expanded form. Yes, an efficient all one coefficients algorithm seems difficult; actually, to me, the nub of it seems similar to this question itself. I suspect they are equivalent in some sense (if so, the promise problem would be begging the question.) I have an algorithm for checking all one which is OK for most common cases; but is exponential in the worst cases, which are rare... I think. I actually hadn't thought of asking it as a question here - maybe I should. Thanks! | |
| Nov 19, 2014 at 1:13 | comment | added | user12859 | @hyperpallium : $\;\;\;$ Does your "no coefficients other than 1" line refer to the expanded form? $\:$ If yes, then you might just have a promise problem, since I don't see any feasible way to check that requirement. $\:$ If no, what does that mean? $\:$ In any case, it may help that you are only dealing with formulas rather than circuits. $\;\;\;\;\;\;\;$ | |
| Nov 18, 2014 at 7:20 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 2 characters in body
|
| Nov 18, 2014 at 7:14 | history | edited | hyperpallium | CC BY-SA 3.0 |
edited title
|
| Nov 18, 2014 at 7:09 | history | edited | hyperpallium | CC BY-SA 3.0 |
edited title
|
| Nov 18, 2014 at 6:58 | history | edited | hyperpallium | CC BY-SA 3.0 |
edited title
|
| Nov 18, 2014 at 3:50 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 49 characters in body
|
| Nov 18, 2014 at 0:21 | vote | accept | hyperpallium | ||
| Nov 16, 2014 at 12:13 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 61 characters in body
|
| Nov 16, 2014 at 11:02 | comment | added | hyperpallium | @TomvanderZanden after reading the reference questions, I think I understand your point about succientness now: if the witness has greater than $P$ length, it can't be verified in $P$ time, and so isn't in $NP$. If the witness exhaustively lists all the failures, it will have exponential length (and it's hard to see how to present it more briefly). | |
| Nov 16, 2014 at 8:41 | answer | added | D.W.♦ | timeline score: 8 | |
| Nov 16, 2014 at 8:28 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 147 characters in body
|
| Nov 16, 2014 at 8:18 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 100 characters in body
|
| Nov 16, 2014 at 7:32 | history | edited | hyperpallium | CC BY-SA 3.0 |
deleted 353 characters in body
|
| Nov 16, 2014 at 5:47 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 54 characters in body
|
| Nov 16, 2014 at 5:40 | comment | added | hyperpallium | @anorton thanks for the terminology! Checking, additive identity ($0$) is a multiplicative annihilator ($a.0=0.a=0$) so that aspect applies; but arithmetic algebra is actually a commutative semiring (because $ab=ba$). Unfortunately, this lack of ordering is a crucial difference from Kleene algebra/regular expressions (where $ab\neq ba$). | |
| Nov 16, 2014 at 3:59 | comment | added | apnorton | You're looking at determining expression equivalence in a semiring. This is related to a Kleene algebra, which, in turn, is related to regular expressions. It might be possible to reduce this problem to determining equivalence of regexes. I'm out of my depth, but that might aid search terms. | |
| Nov 16, 2014 at 3:32 | history | edited | hyperpallium |
edited tags
|
|
| Nov 16, 2014 at 2:58 | history | edited | hyperpallium | CC BY-SA 3.0 |
deleted 12 characters in body
|
| Nov 16, 2014 at 2:53 | history | edited | hyperpallium | CC BY-SA 3.0 |
deleted 12 characters in body
|
| Nov 16, 2014 at 2:45 | history | edited | hyperpallium | CC BY-SA 3.0 |
rewrite to simplify and clarify in response to comments
|
| Nov 16, 2014 at 0:27 | comment | added | hyperpallium | @Raphael, YuvalFilmus thanks, I will study the complexity section. | |
| Nov 16, 2014 at 0:21 | comment | added | hyperpallium | @TomvanderZanden I think I see what you're saying about succientness of proof, for different strategies. But I don't see how it relates to my problem: if I had an algorithm to generate witnesses of inequivalence, then I could just run it, and if it didn't find any, that would prove equivalence. Though it seems quite possible, even likely, that the complexity of finding one witness of inequivalence is much lower than an exhaustive search to determine no such witness exists. (But could also be that worst-case finding the witness is the same complexity as determining none, so maybe NP=coNP) | |
| Nov 15, 2014 at 15:40 | comment | added | Tom van der Zanden | Regarding $NP$ and $coNP$: For all practical purposes, expression equivalence and expression inequivalence are the same problem. But from a complexity theory perspective they're very different: I can convince you very easily that two expressions are inequivalent by demonstrating an input on which they evaluate to different values, but it might be very difficult to show that two expressions are equivalent. Failure to find a witness of inequivalence is proof that they are equivalent, but I can not present that proof in a succinct way. Whether $NP=coNP$ or not is another big open problem. | |
| Nov 15, 2014 at 14:31 | comment | added | Yuval Filmus | @hyperpallium Before asking if a language (i.e. a decision problem) is in NP, it's best if you understood what this means. Perhaps the reference questions that Raphael linked to would help. | |
| Nov 15, 2014 at 12:10 | comment | added | Raphael | If you struggle with the basics, our reference questions may be helpful to you. | |
| Nov 15, 2014 at 10:51 | history | edited | hyperpallium | CC BY-SA 3.0 |
s/np/np-hard/g
|
| Nov 15, 2014 at 10:48 | comment | added | hyperpallium | thanks @TomvanderZanden, that helps! But if failure to find a witness of inequivalence shows the expressions are equivalent, then either can be used to get the solution, so how do $NP$ and $coNP$ differ (for my problem)? I accept them as different approaches, that might inspire different algorithms. Yes, proving no polytime algorithm exists is real hard; but showing my problem is in one of the $NP$ classes ($NP$-hard seems the right now, for "difficult" problems) seemed possible, that would be close enough to "impossible" for me to stop worrying about it. | |
| Nov 15, 2014 at 10:14 | comment | added | Tom van der Zanden | Basic definitions: A problem is in NP if it can be verified in polynomial time. A problem that is NP-hard is "difficult", because if you could solve it in polynomial time you could solve any problem in NP in polynomial time. A problem that is both NP-hard and in NP is NP-complete. "Language" and "problem" are used more or less interchangeably. Failure to find a witness does indeed show they are equivalent. Nobody will be able to prove that a polynomial time solution doesn't exist (or they would have resolved a major open problem in theoretical computer science). | |
| Nov 15, 2014 at 7:27 | comment | added | hyperpallium | In the light comment feedback, I think I should change my question (1) algebra: use familiar high-school arithmetic (2+2=4, 2.3=6 etc) algebra, with $a$, $b$ etc being variables and ask that answers not rely on inverses (substraction, division); (2) complexity: ask for proof that a polynomial time solution does not exist (or, for a polynomial time solution, if one does exist). Of course, answers might still use $NP${,-hard,-complete}, if it can be addressed that way. | |
| Nov 15, 2014 at 7:08 | comment | added | hyperpallium | @YuvalFilmus thanks, though I'm not grasping some terms, and I'm wondering if "is it in $NP$?" means "is it verifiable in polytime?" and not "is it a difficult problem?". I can't expect basic lessons here, but I'll list the terms and my understanding: witness - a solution to the problem that can be verified in P time; "language is in NP"" - I thought NP was for problems, not languages...? If we can find a witness in non-deterministic polynomial time that two expressions are inequivalent, doesn't a failure to find such a witness show they are equivalent? What's the flaw in my reasoning? | |
| Nov 15, 2014 at 3:20 | comment | added | Yuval Filmus | @hyperpallium NP and coNP are not the same. For example, SAT is in NP but probably not in coNP. A language is in NP if there are witnesses for being in the language. It is in coNP if there are witnesses for being outside the language. In your case, an NP witness is a succinct proof that the two expressions are equivalent, while a coNP witness is a succinct proof that the two expressions are inequivalent. The latter is easier to imagine – some word which is accepted by one but not the other. | |
| Nov 15, 2014 at 2:52 | comment | added | hyperpallium | @DavidRicherby I now realize that if I'm going to use $NP$, I actually do need to be clear on the defintions. I have reviewed the definitions a few times (just wikipedia and other web results), though I'm finding it difficult to fit my problem to it. Maybe it's not a good fit...? | |
| Nov 15, 2014 at 2:42 | comment | added | hyperpallium | @DavidRicherby maybe I should ask this question in terms of complexity, not $NP$. I just used $NP$ because it seems to be a well-developed body of knowledge and therefore might have an answer already. | |
| Nov 15, 2014 at 2:39 | comment | added | hyperpallium | @DavidRicherby sorry, I'm not following. I meant that full expansion requires exponential symbols to state (e.g. $\Pi (x_i + y_i)$ expands to $2^n$ terms), and therefore exponential time to output it. Exponential time is worse than polynomial time. er... unless you mean that the sum-of-products algorithm isn't in $NP$ (as it has exponential terms, as you said in your first comment)? | |
| Nov 15, 2014 at 1:46 | comment | added | David Richerby | @hyperpallium "expanding it is NP, because just stating the answer takes exponential space" No! NP is nondeterministic polynomial time: if you're only using polynomial time, you're certainly not using exponential amounts of space. "Everyone knows what is meant by 'in NP'" I'm afraid you need to refresh the definition, there. | |
| Nov 15, 2014 at 1:30 | comment | added | hyperpallium | @DavidRicherby I think my problem is equivalent to arithmetic $+$ and $.$ with variables, if we exclude inverses. If Schwartz–Zippel is the best that can be done, and it requires inverses (subtraction), that seems to suggest that mine is a hard problem, and probably in $NP$. Does that seem right to you? | |
| Nov 15, 2014 at 1:27 | history | edited | hyperpallium | CC BY-SA 3.0 |
edited body
|
| Nov 15, 2014 at 1:21 | comment | added | hyperpallium | @TomvanderZanden yes, solutions solved in polynomial time ($P$) are verifiable in polynomial time ($NP$), so $P \subseteq NP$. But - and maybe I'm wrong here - I feel the precise distinctions between $NP$, $NP-complete$ and $NP-hard$ can overshadow the actual problem; and by abuse of terminology, everyone knows what is meant by "in $NP$". e.g. question title also uses "$NP$". BTW: I stated it as a sequence of expansions/factorings because this is verifiable in P time - coming up with that sequence may take longer. | |
| Nov 15, 2014 at 1:15 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 22 characters in body
|
| Nov 15, 2014 at 0:35 | comment | added | hyperpallium | @IdeaHat expanding it is $NP$, because just stating the answer takes exponential space (BTW: isn't sum-of-products closer to DNF than CNF?). But expanding it is part of one particular algorithm; maybe there's a cleverer way that avoids that. BTW I agree it seems similar to boolean algebra, but I haven't been able to find an equivalence e.g. $x \lor y$ includes both being true; but $x+y$ means either-or. We could use exclusive-or, but it nests differently: $(x \oplus y) \oplus z$ is also true is all the variables are true, whereas $(x+y)+z$ means just one of them (i.e. $\{\{x\},\{y\},\{z\}\}$). | |
| Nov 15, 2014 at 0:20 | comment | added | hyperpallium | @YuvalFilmus I'm not familiar with coNP. Checking wikipedia, it seems to just be the complement. So here, wouldn't that be "are the expressions not equivalent" - it seems an identical question for a decision problem. But probably I don't understand. | |
| Nov 14, 2014 at 22:44 | comment | added | Tom van der Zanden | I'm surprised nobody mentioned this yet, but "if it is in NP I don't need to worry about finding a polynomial algorithm" doesn't make sense. Every problem in P is also in NP. You probably meant to ask whether the problem is NP-complete (or -hard). | |
| Nov 14, 2014 at 19:59 | comment | added | IdeaHat | Hrm...I believe your math rules are similar to that of boolean logic. Expanding it out is similar to the known task of converting a boolean expression to conjuntive normal form, which maps directly to 3SAT which is NP Complete. I'll be betting that a similar proof can show that your logic is also 3SAT-mappable and thus NP. | |
| Nov 14, 2014 at 18:15 | history | tweeted | twitter.com/#!/StackCompSci/status/533322462331555841 | ||
| Nov 14, 2014 at 15:48 | comment | added | Yuval Filmus | You could also ask whether it's in coNP, or do you already know that? | |
| Nov 14, 2014 at 14:12 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 24 characters in body
|
| Nov 14, 2014 at 14:07 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 24 characters in body
|
| Nov 14, 2014 at 13:56 | history | edited | hyperpallium | CC BY-SA 3.0 |
clarify based on comment feedback
|
| Nov 14, 2014 at 13:28 | comment | added | hyperpallium | Thanks @DavidRicherby. Addition and multiplication don't have inverses (I described it as "arithmetic", thinking lack of inverses wouldn't matter, but as you're shown, it's significant in the S-Z lemma). Objects $a$ and $b$ are elements (like symbols in regular expressions). The underlying set is (the set of all) languages of symbols sets - like kleene algebra/regular expressions, but no order (and no star): + is language union; . is union of all combinations of symbol sets in the operand languages. Yes, I meant the sum-of-products algorithm as not in P. I'll edit. | |
| Nov 14, 2014 at 12:51 | comment | added | David Richerby | If the objects are variables, and subtraction is allowed, then you're essentially asking about polynomial identity testing, which has a randomized polynomial time algorithm by the Schwartz–Zippel lemma. $f(x)=g(x)$ iff $f(x)-g(x)=0$ and the basic idea is that a polynomial that isn't identically zero doesn't have many roots so, if you start guessing roots at random and find a lot of roots, there's a high probability that your polynomial was identically zero. | |
| Nov 14, 2014 at 12:50 | comment | added | David Richerby | The question here needs some clarification. What field are you operating over? Are the objects such as "$a$" and "$b$" in your expressions elements of the field or variables? Is it actually a field (i.e., do addition and multiplication have inverses)? Note that sum-of-products doesn't help because $(a_1+b_1)(a_2+b_2)\cdots(a_n+b_n)$ has exponetially many terms. | |
| Nov 14, 2014 at 11:40 | history | edited | hyperpallium | CC BY-SA 3.0 |
added 1 character in body
|
| Nov 14, 2014 at 11:38 | history | edited | Raphael |
edited tags
|
|
| Nov 14, 2014 at 11:30 | review | First posts | |||
| Nov 14, 2014 at 12:40 | |||||
| Nov 14, 2014 at 11:29 | history | asked | hyperpallium | CC BY-SA 3.0 |