Is reforging NP Hard / NP-Complete?

Rogue
I figure I'll cross post this here since rogues are probably much smarter than general discussion.

I've been wondering this for a while now; has reforging ever been proven to be NP-Complete? We take it as a given that it is NP-Hard (although seeing a proof of this would be nice, i.e what problem reduces to reforging), but sometimes I see people claim that it's NP-complete. This implies that we can easily verify whether or not a reforging solution is optimal. Does anyone have any info on this?
Yup, if you can solve REFORGE then you can also solve SUBSET SUM (http://en.wikipedia.org/wiki/Subset_sum_problem).

Actual/thorough Proof
Given an instance of SUBSET SUM, where we have a set S of n integers and a target k, here's how to use a black box for solving REFORGE that will solve SS.

Take a character with n pieces of armor. For each element i in S, give item i haste equal to the value of that element times 2.5 (since reforging only gives 40% of the stat). That is, if the first element in S is 7, then give the first armor piece 7 haste. Give no other stat values to any other items, and do not enchant or gem any of them.

Now, create the following stat priority: Y-Hit >> Haste >> Anything.

Let the yellow hit cap be equal to k.

Reforge. If we have hit the Y-hit cap exactly, then the instance of SUBSET SUM can be solved. If not, then the instance of SUBSET SUM cannot. Since we did this with a single call to our black box and SUBSET SUM is NP-Complete, REFORGE must also be.


Abridged/English "Proof":
The problem mentioned in the proof above, called SUBSET SUM (hard problems are in caps because they are hard) is NP-complete. SUBSET SUM basically says that if I have a pile of treasure where each piece potentially has a different weight but can only carry up to 152 lbs of loot, can I take exactly 152 lbs, or do I have to settle for less? This is almost exactly the same as trying to figure out how close one can get to reaching a cap exactly, so in a highly-simplified version of reforging where we only had two stats - hit and haste - and hit was always better than haste before the cap, reforging would still be at least as hard as SUBSET SUM because in that simple case they are essentially the same problem (can I make the cap exactly without going over?). Of course, in reality reforging is much more complex since there are multiple options and stats to worry about, but it should be pretty clear that that doesn't make the problem any easier to solve.


So yeah, reforging is NP-Complete. There are some tools that simply check every possible configuration, although reforgers nowadays still do a pretty good job at getting quite a high degree of accuracy with what I believe are approximation algorithms. One thing they may also do is limit the options for reforging and then try every possible option, which is quite reasonable. For instance, if crit is your worst stat, then having the program never bother reforging to crit would make sense.

Most importantly, DID I WIN???
THANK YOU SO MUCH.

You are amazing. Did you write up all of those proofs on the fly to respond to my post, or were they previous knowledge for you?

Also if I may inquire, what level of CS education do you have? BS, Masters, Phd? I'm just wondering at what point I can be awesome enough to prove computational complexity problems casually for a video game.

Also I'm glad my intuition to seek out a rogue was correct. Even just googling for this kind of information typically only brought up rogue discussions. I love how we're the class most interested in theorycrafting and computer science / optimization.
05/01/2014 11:23 PMPosted by Claerwynn
You are amazing. Did you write up all of those proofs on the fly to respond to my post, or were they previous knowledge for you?

Haha, thanks! Yeah, I read this post right before going to bed and thought it was interesting. This of course meant that I just had to come up with a reduction!

05/01/2014 11:23 PMPosted by Claerwynn
Also if I may inquire, what level of CS education do you have?

I'm an undergrad. Last semester I took algorithms though so this is all still very fresh in my memory, hence coming up with that reduction on the fly. WAY too many problem sets about that for me not to be quick at such a problem :D.

05/01/2014 11:23 PMPosted by Claerwynn
I love how we're the class most interested in theorycrafting and computer science / optimization.

HELL YEAH WE'RE AWESOME! Good luck with your studies and what not! Are you learning formally through an institution or on your own?

EDIT: Just realized in my first reply I was talking about this haste cap instead of the hit cap. Whoops >.>

EDIT 2: Another mistake I made was that armor should actually get 2.5*v haste, where v is the value of whatever we are copying over. This is because reforging only converts 40% of the stat, and 40% of 2.5v is v. Analysis is the same though, but whoops and that's what I get for doing this stuff past my bed time.
Grr...How did I miss this before? Every time I read things like this I get all angry with myself for not taking more CS classes in college.
What I'm doing now:

#lang racket
(require "stream.ss")

;Given defs (used for testing purposes)

(define IntsFrom$ (lambda (n) (cons$ n (IntsFrom$ (+ n 1)))))
(define Ints$ (IntsFrom$ 0))
(define Evens$ (map$ (lambda (x) (* 2 x)) Ints$))
(define Ones$ (cons$ 1 (Ones$)))
(define Odds$ (+$ Evens$ Ones$))

;Part 1

;RemoveMember-allBLING
(define rember-all$ (λ (x s)
(cond
[(eq? x (car$ s)) (rember-all$ x (cdr$ s))]
[else (cons$ (car$ s) (rember-all$ x (cdr$ s)))])))

;Substitute-allBLING
(define subst-all$ (λ (x y s)
(cond
[(eq? x (car$ s)) (cons$ y (subst-all$ x y (cdr$ s)))]
[else (cons$ (car$ s) (subst-all$ x y (cdr$ s)))])))

;Part 2

;MemberBLING.
(define member$ (λ (x s less-than-or-equal)
(cond
[(and (less-than-or-equal x (car$ s)) (less-than-or-equal (car$ s) x)) #t]
[(less-than-or-equal (car$ s) x) (member$ x (cdr$ s) less-than-or-equal)]
[else #f])))

;Part 3

;Print for debugging
(member$ 13 Evens$ <=)


Feel better?
Never heard of racket before.

Looks ugly.
It's Scheme, which is kinda like LISP. LISP, of course, stands for Lots of Incredibly Stupid Parenthases.
05/02/2014 03:26 PMPosted by Haileaus
It's Scheme, which is kinda like LISP. LISP, of course, stands for Lots of Incredibly Stupid Parenthases.
Seems inefficient.

Ya know, from the perspective of a high school senior with 2 weeks left of school.
Don't have the energy to look at your code right now (just got back from yet another long day of working on an Operating Systems project), but I can answer the easy questions. I'm currently a senior in an undergrad CS major, and I'm taking a computational complexity class right now. We're only just starting to dig into reductions, and I love the material, so I figured reforging would be a really cool way of getting more into the material. I wanted to come up with the proof myself but I haven't quite learned enough yet to be at that point.

By the way...coding an operating system is terrible. I wish I could just do light programming classes and heavy math classes as some sort of "focus" in my major, but that isn't a thing.
05/02/2014 09:17 PMPosted by Scrublordxo
a high school senior with 2 weeks left of school.

I'm so sorry.

05/02/2014 09:47 PMPosted by Claerwynn
By the way...coding an operating system is terrible. I wish I could just do light programming classes and heavy math classes as some sort of "focus" in my major, but that isn't a thing.

That's too bad. My school also doesn't do specializations for the major, mostly because it has under 3000 students. That said I'm taking game design and artificial intelligence next semester which aren't required and will hopefully help prepare me for working in the gaming industry, because that's what I'm looking at atm. In general though I like coding as long as the project is interesting.
05/01/2014 10:21 PMPosted by Haileaus
There are some tools that simply check every possible configuration, although reforgers nowadays still do a pretty good job at getting quite a high degree of accuracy with what I believe are approximation algorithms.

While they both use approximate algorithms both AMR and ShC have a weak optimality guarantee on most gear sets. Both tools use a branch and bound algorithm that allows full search tree enumeration to be tractable within reasonable time (1-2 seconds) by pruning branches that cannot possibly yield high results. Reforgelite (although it has fallen out of favor somewhat) uses a random walk/hill-climbing algorithm that will typically get close to optimality but you have to run the algorithm several times until it settles.

05/02/2014 09:17 PMPosted by Scrublordxo
05/02/2014 03:26 PMPosted by Haileaus
It's Scheme, which is kinda like LISP. LISP, of course, stands for Lots of Incredibly Stupid Parenthases.
Seems inefficient.

Ya know, from the perspective of a high school senior with 2 weeks left of school.

Lisp (and functional programming in general) is worth learning and in any good CS curriculum you will cover it. First functional programming requires a very unique way of thinking about programs compared to traditional imperative programming (C style languages) because functions exist in a strictly mathematical sense of mapping inputs to outputs without the concept of state or side effects. This can allow some very elegant programs. Another advantage of functional programming in a CS curriculum is that is forces you to learn recursion, recursion can often be hard to grok in a traditional imperative language but in functional programming the natural relationship to inductive proofs and methods becomes obvious. Finally while very few people use a pure functional language like Lisp or Haskell a lot of the ideas of functional programming are very trendy. Concepts like lambdas and more generally first class functions are found in a lot of modern languages, C++x11 added lambda support, I believe Java 8 and C# have them as well and in scripting languages (Perl, Ruby, Python for example) they are very common and very powerful.

If you are interested in learning about functional programming the famous MIT text Structure and Interpretation of Computer Programs is available for free online.
http://mitpress.mit.edu/sicp/full-text/book/book.html

05/02/2014 09:47 PMPosted by Claerwynn
By the way...coding an operating system is terrible.

There is a certain elegance to the linux kernel. Yeah a lot of it is really unholy C hacks that are rightly shunned but there are some really elegant ideas in there. One of my favorites is the concept of the list_head. For those who haven't hacked around in the linux kernel a list_head is a struct that you can add to any other struct to make it into a linked list. Since so much of the kernel operates on linked lists having an optimized way to traverse lists of arbitrary objects is really powerful and important.
Yes, functional programming is great! I personally really enjoy Haskell, and it's become one of my favorite languages to program in since I learned it. More importantly, learning it really helped me become a better programmer.

05/03/2014 12:16 PMPosted by Fierydemise
There is a certain elegance to the linux kernel. Yeah a lot of it is really unholy C hacks that are rightly shunned but there are some really elegant ideas in there. One of my favorites is the concept of the list_head. For those who haven't hacked around in the linux kernel a list_head is a struct that you can add to any other struct to make it into a linked list. Since so much of the kernel operates on linked lists having an optimized way to traverse lists of arbitrary objects is really powerful and important.


Sure, when you examine the abstraction of it it can be pretty and nice. But actually coding it seems to be really messy and as you said, filled with C hacks.

Join the Conversation

Return to Forum