Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sav08:homework08 [2008/09/15 15:06] vkuncak |
sav08:homework08 [2008/09/15 15:56] vkuncak |
||
|---|---|---|---|
| Line 23: | Line 23: | ||
| \] | \] | ||
| By generalizing the objective function to reals, we can solve non-linear but polynomial optimization problems using quantifier elimination over reals. | By generalizing the objective function to reals, we can solve non-linear but polynomial optimization problems using quantifier elimination over reals. | ||
| + | |||
| ===== Problem 2 ===== | ===== Problem 2 ===== | ||
| Line 40: | Line 41: | ||
| If you cannot solve the problem in its entirety, write observations that you could obtain. You are allowed (but not required) to use any references (books, papers) that you can find (but it may be easier to solve the problem on your own). You must cite any references that you used. You need not write down in great detail explanations of simple facts, but if you omit any proof steps make sure that they indeed simple. | If you cannot solve the problem in its entirety, write observations that you could obtain. You are allowed (but not required) to use any references (books, papers) that you can find (but it may be easier to solve the problem on your own). You must cite any references that you used. You need not write down in great detail explanations of simple facts, but if you omit any proof steps make sure that they indeed simple. | ||
| - | Added afterwards: | + | Solution (added afterwards): |
| - | * Läuchli, H., Leonard, J.: On the elementary theory of linear order. Fund. Math. 59, 109–116 (1966) (Thanks to Yuri Gurevich, who also mentions that result follows from decidability of S2S) | + | * {{sav08:laeuchlileonard66linearorder.pdf|Läuchli, H., Leonard, J.: On the elementary theory of linear order. Fund. Math. 59, 109–116 (1966)}} (Thanks to Yuri Gurevich, who also mentions that result follows from decidability of S2S) |
| * [[http://www.jstor.org/sici?sici=0022-4812%28196806%2933%3A2%3C287%3AOTETOL%3E2%2E0%2ECO%3B2-I&origin=euclid|review]], {{sav08:review-linearorder.pdf|review pdf}} | * [[http://www.jstor.org/sici?sici=0022-4812%28196806%2933%3A2%3C287%3AOTETOL%3E2%2E0%2ECO%3B2-I&origin=euclid|review]], {{sav08:review-linearorder.pdf|review pdf}} | ||
| + | Somewhat related papers: | ||
| * {{sav08:ehrenfeuchtordergames.pdf|A. Ehrenfeucht. An application of games to the completeness problem for formalized theories}}. Fund. Math., 49:129–141, 1961. | * {{sav08:ehrenfeuchtordergames.pdf|A. Ehrenfeucht. An application of games to the completeness problem for formalized theories}}. Fund. Math., 49:129–141, 1961. | ||
| * {{sav08:gurevich-thesis.pdf|Y. Gurevich: Elementary Properties of Ordered Abelian Groups}} | * {{sav08:gurevich-thesis.pdf|Y. Gurevich: Elementary Properties of Ordered Abelian Groups}} | ||