My Math Forum Complex Number Factoring is NPComplete

 Complex Analysis Complex Analysis Math Forum

 December 15th, 2014, 10:39 AM #1 Senior Member   Joined: Jan 2013 Posts: 209 Thanks: 3 Complex Number Factoring is NPComplete Subset Sum (given n integers, answer does any nonempty subset sum to 0) of n integers can be calculated as multiplying n complex numbers (each of magnitude 1) which are all scaled by the sum of all the integers so it can wrap around less than a half turn either direction in total. The multiply of 2 complex numbers whose magnitude is 1 adds their angles around complex unit circle. Negative angle is the same as dividing by the positively angled complex number. Angle is normally ambiguous since it repeats on intervals of 2*pi, but since its scaled so it cant wrap around in total, each angle it can reach uniquely represents an integer. Complex Number Factoring is NPComplete, based on that alone. Here's some more info... If you multiply all the integers by 2, offset each of them by half their value, and move that value into the target sum of the subset to find, and do the same for the new target sum, then subset sum can be represented as a choice of negative or positive of the same value for each integer translated that way. On complex unit circle, it looks like rotating clockwise vs counterclockwise for each integer thats included or not. To solve Subset Sum you would factor 1. Its not a root of unity. Its factors of unity limited to a set of possible factors. It can also be represented as all being positive angled magnitude 1 complex numbers and looking for a Subset Multiply that equals that complex number. Integer Factoring is to Multiply as Complex Number Factoring is to Plus.
December 15th, 2014, 11:04 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by BenFRayfield Complex Number Factoring is NPComplete, based on that alone.
No. You don't know what you're talking about.

 Tags complex, factoring, npcomplete, number

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post BenFRayfield Computer Science 3 August 25th, 2013 07:07 AM BenFRayfield Applied Math 0 August 23rd, 2013 09:57 AM agelaki11 Complex Analysis 5 April 25th, 2013 02:03 PM mmxxmm Number Theory 1 April 22nd, 2012 12:59 PM TsAmE Complex Analysis 1 October 18th, 2010 04:38 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top