Currently the best graphics cards to mine Bitcoins are all AMDs. What should be changed in the Bitcoin protocol to make the alternative version of Bitcoins better mined by NVIDIA graphics cards? Could there be a protocol that would support both of the graphics cards produces in more or less equal way?
The specific reason that AMD cards are more efficient for Bitcoin mining is twofold and the answer to this question depends on both reasons:
Combining the two reasons above results in an overall 3x-5x faster generation of SHA256 checksums. However the two effects are not equal: Effect 1 leads to approximately 2x-3x Nvidia's performance all on its own, with Effect 2 accounting for about 1.7x performance advantage. Even if you were to choose a hashing algorithm that made less use of the BIT_ALIGN_INT instruction AMD cards would still be 2x-3x faster for hashing algorithms in general. This is because such algorithms are explicitly designed to be simple binary operations which AMD's simple ALUs can handle just as well as Nvidia's more complex ALUs.
In order to choose an algorithm which would perform better on Nvidia cards than AMD cards, you would not only have to eliminate scenarios such as #2 above where a specific instruction happens to be better implemented on one card than the other, you would also have to choose an algorithm with math complex enough that Nvidia's higher-end ALUs get the chance to individually shine. To my knowledge no such algorithm exists.
To back up my statements, here is some example data from oclHashcat's web site. The table below compares actual performance measurements from similarly priced AMD and Nvidia cards for the MD5, SHA1, MD4, NTLM and SHA256 algorithms, among others.
Keep in mind that in comparing PC1/2 and PC3/4 that the Nvidia cards actually have higher clock speeds in both cases and still perform worse. In no case did Nvidia's performance approach the performance of a similarly priced AMD card, and to my knowledge no currently implemented algorithm performs sufficiently complex mathematics to make use of the more advanced ALUs on Nvidia's cards.
In short, Nvidia cards are like a small room with several fairly intelligent people, each capable of complex mathematics while AMD's cards are like a sweatshop. Hash algorithms are the computing equivalent of mass-producing name-brand tennis shoes and so the AMD "sweatshop" card will always outperform.
David Perry answer is solid I would just add that what will make NVidia cards more competitive isn't changing bitcoin or making an alternative but instead market forces will force NVidia to improve integer performance.
Nvidia is well aware their integer performance is abysmall and each generation AMD pulls further ahead. In the past this wasn't very important because floating point math is used for graphics, physics, and most high performance computing work. Still abysmal integer performance is a weak point in their lineup and as GPGPU becomes more mainstream it will matter more and more. Over time expect GPGPU solutions for everything from speeding up SSL handshakes to whole hard drive encryption. Unless Nvidia simply want to hand the entire crypto market to AMD on a silver platter they will be forced to improve integer performance. How they do this isn't really material (unless you work for NVidia), market forces will require NVidia to do so or they face declining marketshare.