
Complex Analysis Complex Analysis Math Forum 
 LinkBack  Thread Tools  Display Modes 
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  

Tags 
complex, factoring, npcomplete, number 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Many think Chess is NPComplete so is Deep Blue general AI  BenFRayfield  Computer Science  3  August 25th, 2013 07:07 AM 
NPComplete  Superfluidity and if accurate Navier Stokes  BenFRayfield  Applied Math  0  August 23rd, 2013 09:57 AM 
Factoring in Complex Field  agelaki11  Complex Analysis  5  April 25th, 2013 02:03 PM 
Number Factoring  mmxxmm  Number Theory  1  April 22nd, 2012 12:59 PM 
Finding real number in complex number  TsAmE  Complex Analysis  1  October 18th, 2010 04:38 PM 