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?

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???

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 ClaerwynnYou 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 ClaerwynnAlso 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 ClaerwynnI 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.

#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.

Looks ugly.

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

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

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 Scrublordxoa high school senior with 2 weeks left of school.

I'm so sorry.

05/02/2014 09:47 PMPosted by ClaerwynnBy 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 HaileausThere 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 ScrublordxoSeems inefficient.05/02/2014 03:26 PMPosted by HaileausIt's Scheme, which is kinda like LISP. LISP, of course, stands for Lots of Incredibly Stupid Parenthases.

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 ClaerwynnBy 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.

05/03/2014 12:16 PMPosted by FierydemiseThere 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.