Mathematics desk
< June 3	<< May \| June \| Jul >>	June 5 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 4[edit]

Finding angle between vectors in two dimensions[edit]

How would you find the angle between two vectors in the coordinate plane, given their endpoint and assuming they start at the origin, WITHOUT using the dot product or similar (a.k.a. advanced) properties. An equation using the coordinates would be nice! dude❶❽❶❽ (talk) 01:06, 4 June 2010 (UTC)[reply]

You should see that there are always two angles between any two vectors in the conditions you describe. Let's deal with the smallest one (which we'll call angle BAC), since witht that you can easily find the bigger one. If you know the two vectors' start and endpoints, then you also know their lengths (call them AB and AC, A being (0,0)). Use the distance formula to find the distance between the vectors' endpoints (BC). Then use the Law of Cosines to find the angle:

BC^{2}=AB^{2}+AC^{2}-2(AB)(AC)(\cos m\angle BAC)

. Elementary mathematics. 76.199.147.211 (talk) 02:12, 4 June 2010 (UTC)[reply]

TO simplify even further

m\angle BAC=\arccos {\frac {BC^{2}-AB^{2}-AC^{2}}{-2(AB)(AC)}}

Oh yeah. That was dumb of me, I recently learned Law of Cos. Thank you! dude❶❽❶❽ (talk) 02:38, 4 June 2010 (UTC)[reply]

But, of course, the cosine rule is really the dot product in disguise, since

AB^{2}+AC^{2}-BC^{2}=(B_{1}^{2}+B_{2}^{2})+(C_{1}^{2}+C_{2}^{2})-((C_{1}-B_{1})^{2}+(C_{2}-B_{2})^{2})=2(B_{1}C_{1}+B_{2}C_{2})=2{\overrightarrow {AB}}.{\overrightarrow {AC}}

Gandalf61 (talk) 16:32, 5 June 2010 (UTC)[reply]

Co-NP[edit]

On our Co-NP page it says that the complemenet to subset sum is, "Does every subset sum to a nonzero number?" Wouldn't a yes/no answer to this imply a no/yes answer to "Does there exist a subset that sums to zero?"? If so, then why is subset sum not equivalent to its complement since an algorithm solving one solves the other? 66.202.66.78 (talk) 07:26, 4 June 2010 (UTC)[reply]

The difference is in the asymmetry between "yes" and "no" in the definition of NP. A problem is in NP if "yes" answers have a proof that can be verified quickly - there's no similar requirement for "no" answers. For "Does every subset sum to a nonzero number?", it is not known that a positive answer can be easily verified, so it's not known to be in NP. But a negative answer, accompanied with a counterexample, can be trivially verified - so it's in co-NP.

You are correct that if a deterministic polynomial-time algorithm solves an NP-complete problem, then it trivially also solves its complement, so in this case P = NP = co-NP. But if P ≠ NP then also P ≠ co-NP and possibly NP ≠ co-NP. -- Meni Rosenfeld (talk) 07:42, 4 June 2010 (UTC)[reply]

I understand that if we had a polytime algorithm to solve subset sum, then NP = co-NP; what I meant was that since we can reduce any algorithm solving subset sum to one solving the above descion problem in polytime, why doesn't this imply NP = co-NP? In other words, let A be any algorithim solving subset sum and let B flip yes to no and no to yes, doesn't running B on the output of A solve co-Subset Sum, and if so, why doesn't this imply NP = co-NP? 66.202.66.78 (talk) 08:05, 4 June 2010 (UTC)[reply]

I thought co-NP = NP implied P = NP?66.202.66.78 (talk) 08:06, 4 June 2010 (UTC)[reply]

Since the word solving here seems unlcear, when I say an algorithm solving subset sum, I am talking about any algorithm, not just polytime ones:) 66.202.66.78 (talk) 08:12, 4 June 2010 (UTC)[reply]

Last edit to this rush of edits, I swear. I was wrong about the co-NP = NP implies P = NP; sorry. 66.202.66.78 (talk) 08:16, 4 June 2010 (UTC)[reply]

[ec] Because "an algorithm solving subset sum" has nothing to do with it being in NP. Subset-sum is in NP because instances which have a positive answer also have a certificate which can be polynomially verified.

Presumably, P ≠ NP and NP ≠ co-NP. In this case:

Solving a subset-sum instance requires super-polynomial time in the worst case - it is not in P.
Solving co-subsetsum instance requires super-polynomial time in the worst case - it is not in P.
If the answer to an instance of subset-sum is "yes", then there is a certificate (a subset with a sum of 0) that, once we have it, anyone can polynomially verify that the answer is indeed "yes". It is in NP.
There are instances of subset-sum for which the answer is "no", and there is no certificate that can be used to easily verify it. It is not in co-NP.
If the answer to an instance of co-subsetsum is "no", then there is a certificate (a subset with a sum of 0) that, once we have it, anyone can polynomially verify that the answer is indeed "no". It is in co-NP.
There are instances of co-subsetsum for which the answer is "yes", and there is no certificate that can be used to easily verify it. It is not in NP.

To the best of my knowledge, co-NP = NP does not imply P=NP. The converse is true, though. -- Meni Rosenfeld (talk) 08:28, 4 June 2010 (UTC)[reply]

I see, for some reason I was thinking that X and Y are two decison problems and A and algorithm solving both of them, then they were both equal; so, even if the same algorithm(flipping yes and no) solves subsum and cosubsum, they are still different. I'm not sure why I was thinking what I was, thank you:) 66.202.66.78 (talk) 09:00, 4 June 2010 (UTC)[reply]

The most common notion of reduction in this area, used in the definition of NP-completeness for instance, is polynomial-time many-one reduction (aka Karp reduction). Subset sum is not many-one reducible to its complement (unless NP = coNP). The idea of flipping the yes/no outcome of an algorithm only gives a polynomial-time Turing reduction (aka Cook reduction), or better, a tt-reduction. Unlike many-one reduction, NP is not closed under tt- or Turing-reductions (unless NP = coNP, again).—Emil J. 10:10, 4 June 2010 (UTC)[reply]

Drawing a quadrilateral?[edit]

I have been given 4 side lengths- 9, 10, 11 and 12 cm.

Is there a way to calculate the maximum are bound by these dimensions?

I must create a polygon with the maximum area, inscribed in a circle. Are the two the same (ie. does a polygon with given side lengths have maximum area when each vertex touches a point in a circle)?

Is there a program I can use to help me with this? The shape must be drawn within an accuracy of one-tenth of a millimeter.

Thanks in advance!

-PerfectProposal 14:31, 4 June 2010 (UTC)[reply]

I can totally help with this - see Brahmagupta's formula - it should be exactly what you're looking for, along with the further material linked at the end. SamuelRiv (talk) 17:44, 4 June 2010 (UTC)[reply]

The Brahmagupta's formula article doesn't say, however, whether a quadrilateral inscribed in a circle is the maximum possible area for any arrangement of four sides. It might be, but I am not sure.

My intuition says that the arrangement of four sides that yields the largest circle that can be inscribed within the quadrilateral, would correspond to the largest area quadrilateral.

I can think of iterative methods to do this too. Connect the four sides, then adjust the vertex angle of one side (which will control all the other corner angles) until a maximum area is found. Repeat for a different arrangement of sides and then pick the largest area. ~Amatulić (talk) 18:35, 4 June 2010 (UTC)[reply]

Brahmagupta's formula#Extension to non-cyclic quadrilaterals : "It follows from this fact that the area of a cyclic quadrilateral is the maximum possible area for any quadrilateral with the given side lengths." Maybe the article should say that earlier on? --Qwfp (talk) 19:17, 4 June 2010 (UTC)[reply]

Ah, thanks, I missed that sentence. ~Amatulić (talk) 19:37, 4 June 2010 (UTC)[reply]

That's excellent- thanks. Is there a piece of software I can use to assist me in drawing the cyclic quadrilateral? I imagine it'd be rather difficult to draw by hand with that level of accuracy. PerfectProposal 14:18, 5 June 2010 (UTC)[reply]

Can I get GeoGebra to do it for me? I've made a quadrilateral, but can I ask it to make a cyclic quadrilateral, without trial and error? PerfectProposal 16:38, 5 June 2010 (UTC)[reply]

Quadrilateral 2d shape[edit]

Hello. The shape produced by subtracting a rectangle from within another rectangle (eg the outer perimeter but not of zero thickness) - I need to write a technical description and am having trouble describing this shape - does it have a name? Thanks.87.102.32.39 (talk) 23:04, 4 June 2010 (UTC)[reply]

Well, the equivalent with circles is called an annulus. I've never heard of a name for it with rectangles. You could call it a "rectangular annulus", I suppose, and people would probably understand (you should still include a definition, or at least a picture). One issue that comes up with rectangles but not circles is orientation - are the sides of the inner rectangle parallel to the sides of the outer one? That might affect the name, if there is one. --Tango (talk) 02:16, 5 June 2010 (UTC)[reply]

Yes parallel (and the centres coincident) (like a window frame).87.102.32.39 (talk) 02:19, 5 June 2010 (UTC)[reply]

Try 'rectangular border of thickness t and external dimensions x by y'. -- SGBailey (talk) 05:10, 5 June 2010 (UTC)[reply]

Why not call it a frame then ? Bo Jacoby (talk) 07:47, 5 June 2010 (UTC).[reply]

I suppose I could.87.102.32.39 (talk) 10:43, 5 June 2010 (UTC)[reply]

I will use rectangular frame that seems non ambiguous. Thanks.

87.102.43.94 (talk) 15:39, 5 June 2010 (UTC)[reply]

Resolved