Talk:Interfrac
Computational class
This is at least NP-complete NP-hard, because you can implement the wikipedia:subset sum problem in it.
It may well have a higher computational class, though; it's not obvious that you can't program in this. It reminds me a bit of a zero-dimensional version of the wikipedia:Post correspondence problem. --ais523 21:00, 9 March 2019 (UTC)
- Yeah, I was thinking the same thing. It was actually specifically inspired by the PCP, though I hadn't thought of it as a zero-dimensional version. That's an interesting observation Orby (talk) 21:04, 9 March 2019 (UTC)
- After further discussion in #esoteric, we decided that this is almost certainly NP-complete (at least, it's decidable using integer linear programming, which means it's definitely sub-TC). If you remove the requirement to match a defined input (instead checking to see if any input works), it's trivially decidable (some input works if and only if there are fractions a/b and c/d, not necessarily distinct, with a≤b and c≥d; simply take (c-d) copies of the former and (b-a) copies of the latter, and both numerator and denominator add up to bc-ad; this is an invalid construction if a=b, but in that case, simply take one copy of a/b, and numerator and denominator add up to a). --ais523 01:27, 10 March 2019 (UTC)
- Integer linear programming (as a decision problem without objective function, which is all we need for Interfrac) is NP-complete; membership in NP is shown, for example, in http://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf ... so Interfrac with input is NP-complete Int-e (talk) 07:20, 14 March 2019 (UTC)
- After further discussion in #esoteric, we decided that this is almost certainly NP-complete (at least, it's decidable using integer linear programming, which means it's definitely sub-TC). If you remove the requirement to match a defined input (instead checking to see if any input works), it's trivially decidable (some input works if and only if there are fractions a/b and c/d, not necessarily distinct, with a≤b and c≥d; simply take (c-d) copies of the former and (b-a) copies of the latter, and both numerator and denominator add up to bc-ad; this is an invalid construction if a=b, but in that case, simply take one copy of a/b, and numerator and denominator add up to a). --ais523 01:27, 10 March 2019 (UTC)
Mathematics
This could also be viewed as being the complex numbers, or at least the ones that take integer values. We can translate the equation (a / b) + (c / d) = (a + c) / (b + d) into (a + bi) + (c + di) = (a + c) + (b + d)i. The correct input can be found by dividing through by 1 + i. Plokmijnuhby (talk) 17:10, 11 March 2019 (UTC)
Proof that your formula is invalid!
In fact, I believe I can prove that your formula is invalid. (No wonder why the authorities are trying to correct you.)
(1/2)+(1/5) 0.5+0.2 0.7 Using your conversion: (1/2)+(1/5) (1+1)/(2+5) 2/7 0.285714285714... You can't believe this? (1/2)+(1/5) -> (a/b)+(c/d) (1+1)/(2+5) -> (a+c)/(b+d)
Why your formula is invalid
You are saying that you don't need reduction of fractions to a common denominator when you mentioned the formula. If you write the formula down as fractions you will realize that you are directly adding the numerators and denominators together.
I am not trying to make you feel bad; a wrong-formula-based language can be quite useful!