My Math Forum  

Go Back   My Math Forum > College Math Forum > Complex Analysis

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.
BenFRayfield is offline  
December 15th, 2014, 11:04 AM   #2
Global Moderator
CRGreathouse's Avatar
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

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

  My Math Forum > College Math Forum > Complex Analysis

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

Copyright © 2019 My Math Forum. All rights reserved.