Existential theory of the reals
ಗಣಿತದ ತರ್ಕಶಾಸ್ತ್ರ, ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತ ಮತ್ತು ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ, ವಾಸ್ತವಿಕಗಳ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತವು ರೂಪದ ಎಲ್ಲಾ ನಿಜವಾದ ವಾಕ್ಯಗಳ ಗುಂಪಾಗಿದ್ದು, ಅಲ್ಲಿ ಅಸ್ಥಿರಗಳನ್ನು ನೈಜ ಸಂಖ್ಯೆಯ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುವಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಅಲ್ಲಿ ನೈಜ ಬಹುಪದಗಳ ಸಮಾನತೆಗಳು ಮತ್ತು ಅಸಮಾನತೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕ್ವಾಂಟಿಫೈಯರ್-ಫ್ರೀ ಸೂತ್ರವಾಗಿದೆ. ಸೂತ್ರಕ್ಕೆ ಬದಲಿಸಿದಾಗ, ಅದು ನಿಜವಾಗುವಂತೆ ಮಾಡುವ ಎಲ್ಲಾ ಅಸ್ಥಿರಗಳಿಗೆ ಮೌಲ್ಯಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಾದರೆ ಈ ರೂಪದ ವಾಕ್ಯವು ನಿಜವಾಗಿದೆ. ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯೆಂದರೆ, ಅಂತಹ ಪ್ರತಿಯೊಂದು ವಾಕ್ಯಕ್ಕೂ, ಅದು ನಿಜವೇ ಅಥವಾ ಸುಳ್ಳೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಸಮಾನವಾಗಿ, ನೀಡಲಾದ ಅರೆ ಬೀಜಗಣಿತದ ಸೆಟ್ ಖಾಲಿಯಾಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಈ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ ಮತ್ತು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ. ನಲ್ಲಿದೆ, ಇದು ಅಸ್ತಿತ್ವವಾದದ ಕ್ವಾಂಟಿಫೈಯರ್ಗಳಿಗೆ ನಿರ್ಬಂಧವಿಲ್ಲದೆ ವಾಸ್ತವದ ಮೊದಲ-ಕ್ರಮಾಂಕದ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಹೇಳಿಕೆಗಳನ್ನು ನಿರ್ಧರಿಸಲು ಆಲ್ಫ್ರೆಡ್ ಟಾರ್ಸ್ಕಿಯ ಕ್ವಾಂಟಿಫೈಯರ್ ಎಲಿಮಿನೇಷನ್ ಕಾರ್ಯವಿಧಾನಕ್ಕಿಂತ ಗಮನಾರ್ಹವಾಗಿ ಕಡಿಮೆ ಸಂಕೀರ್ಣತೆಯನ್ನು ನೀಡುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಆಚರಣೆಯಲ್ಲಿ, ಮೊದಲ-ಕ್ರಮಾಂಕದ ಸಿದ್ಧಾಂತದ ಸಾಮಾನ್ಯ ವಿಧಾನಗಳು ಈ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಆದ್ಯತೆಯ ಆಯ್ಕೆಯಾಗಿ ಉಳಿದಿವೆ. ಈ ರೂಪದ ಸಮಾನ ವಾಕ್ಯಗಳಾಗಿ ಅನುವಾದಿಸಬಹುದಾದ ಗಣನೆಯ ಸಮಸ್ಯೆಗಳ ವರ್ಗವನ್ನು ವಿವರಿಸಲು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ರಚನಾತ್ಮಕ ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಇದು ಎನ್. ಪಿ. ಮತ್ತು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ ನಡುವೆ ಇದೆ. ಜ್ಯಾಮಿತೀಯ ರೇಖಾಚಿತ್ರ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಅನೇಕ ನೈಸರ್ಗಿಕ ಸಮಸ್ಯೆಗಳು, ವಿಶೇಷವಾಗಿ ಜ್ಯಾಮಿತೀಯ ಛೇದಕ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಗುರುತಿಸುವ ಮತ್ತು ರೇಖಾಚಿತ್ರ ರೇಖಾಚಿತ್ರಗಳ ಅಂಚುಗಳನ್ನು ಕ್ರಾಸಿಂಗ್ಗಳೊಂದಿಗೆ ನೇರಗೊಳಿಸುವ ಸಮಸ್ಯೆಗಳು, ಈ ವರ್ಗಕ್ಕೆ ಸೇರಿವೆ ಮತ್ತು ಅವು ಪೂರ್ಣಗೊಂಡಿವೆ. ಇಲ್ಲಿ, ಸಂಪೂರ್ಣತೆ ಎಂದರೆ, ವಾಸ್ತವದ ಮೇಲೆ ಅನಿಯಂತ್ರಿತ ವಾಕ್ಯದಿಂದ ಕೊಟ್ಟಿರುವ ಸಮಸ್ಯೆಯ ಸಮಾನ ನಿದರ್ಶನವಾಗಿ, ವ್ಯತಿರಿಕ್ತ ದಿಕ್ಕಿನಲ್ಲಿ ಅನುವಾದವಿದೆ ಎಂದರ್ಥ. ಹಿನ್ನೆಲೆ ಗಣಿತದ ತರ್ಕಶಾಸ್ತ್ರದಲ್ಲಿ, ಒಂದು ಸಿದ್ಧಾಂತವು ಒಂದು ನಿಗದಿತ ಚಿಹ್ನೆಗಳ ಗುಂಪನ್ನು ಬಳಸಿಕೊಂಡು ಬರೆಯಲಾದ ವಾಕ್ಯಗಳ ಗುಂಪನ್ನು ಒಳಗೊಂಡಿರುವ ಒಂದು ಔಪಚಾರಿಕ ಭಾಷೆಯಾಗಿದೆ. ನೈಜ ಮುಚ್ಚಿದ ಕ್ಷೇತ್ರಗಳ ಮೊದಲ-ಕ್ರಮಾಂಕದ ಸಿದ್ಧಾಂತವು ಈ ಕೆಳಗಿನ ಚಿಹ್ನೆಗಳನ್ನು ಹೊಂದಿದೆಃ ಸ್ಥಿರಾಂಕಗಳು 0 ಮತ್ತು 1, ಅಸ್ಥಿರಗಳ ಎಣಿಸಬಹುದಾದ ಸಂಗ್ರಹ, ಸೇರ್ಪಡೆ, ವ್ಯವಕಲನ, ಗುಣಾಕಾರ, ಮತ್ತು (ಐಚ್ಛಿಕವಾಗಿ) ವಿಭಜನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳು, ಚಿಹ್ನೆಗಳು <, ≤, =, ±,>, ಮತ್ತು ನೈಜ ಮೌಲ್ಯಗಳ ಹೋಲಿಕೆಗಳಿಗೆ, ತಾರ್ಕಿಕ ಸಂಯೋಜಕಗಳು, ≤, ≤, ಮತ್ತು ≤, ಆವರಣಗಳು, ಮತ್ತು ಸಾರ್ವತ್ರಿಕ ಕ್ವಾಂಟಿಫೈಯರ್ ಮತ್ತು ಅಸ್ತಿತ್ವವಾದದ ಕ್ವಾಂಟಿಫೈಯರ್ ಈ ಚಿಹ್ನೆಗಳ ಅನುಕ್ರಮವು ವ್ಯಾಕರಣಾತ್ಮಕವಾಗಿ ಉತ್ತಮವಾಗಿ ರೂಪುಗೊಂಡಿದ್ದರೆ, ಅದರ ಎಲ್ಲಾ ಅಸ್ಥಿರಗಳನ್ನು ಸರಿಯಾಗಿ ಪ್ರಮಾಣೀಕರಿಸಿದರೆ, ಅದು ನಿಜವಾದ ಮೊದಲ-ಕ್ರಮಾಂಕದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಸೇರಿದ ವಾಕ್ಯವನ್ನು ರೂಪಿಸುತ್ತದೆ, ಮತ್ತು (ನೈಜ ಸಂಖ್ಯೆಗಳ ಬಗ್ಗೆ ಗಣಿತದ ಹೇಳಿಕೆಯಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸಿದಾಗ) ತಾರ್ಸ್ಕಿ ತೋರಿಸಿದಂತೆ, ಈ ಸಿದ್ಧಾಂತವನ್ನು ಸ್ವಯಂಸಿದ್ಧ ರೂಪರೇಖೆ ಮತ್ತು ಸಂಪೂರ್ಣ ಮತ್ತು ಪರಿಣಾಮಕಾರಿ ನಿರ್ಧಾರ ಪ್ರಕ್ರಿಯೆಯಿಂದ ವಿವರಿಸಬಹುದುಃ ಪ್ರತಿ ಸಂಪೂರ್ಣ ಪರಿಮಾಣಾತ್ಮಕ ಮತ್ತು ವ್ಯಾಕರಣಾತ್ಮಕ ವಾಕ್ಯಕ್ಕೆ, ವಾಕ್ಯ ಅಥವಾ ಅದರ ನಿರಾಕರಣೆಯನ್ನು (ಆದರೆ ಎರಡೂ ಅಲ್ಲ) ಸ್ವಯಂಸಿದ್ಧಗಳಿಂದ ಪಡೆಯಬಹುದು. ಅದೇ ಸಿದ್ಧಾಂತವು ಪ್ರತಿ ನೈಜ ಮುಚ್ಚಿದ ಕ್ಷೇತ್ರವನ್ನು ವಿವರಿಸುತ್ತದೆ, ಕೇವಲ ನೈಜ ಸಂಖ್ಯೆಗಳಲ್ಲ. ಆದಾಗ್ಯೂ, ಈ ಸೂತ್ರಗಳಿಂದ ನಿಖರವಾಗಿ ವಿವರಿಸಲಾಗದ ಇತರ ಸಂಖ್ಯಾ ವ್ಯವಸ್ಥೆಗಳಿವೆ; ನಿರ್ದಿಷ್ಟವಾಗಿ, ವಾಸ್ತವಿಕ ಸಂಖ್ಯೆಗಳ ಬದಲಿಗೆ ಪೂರ್ಣಾಂಕಗಳಿಗೆ ಅದೇ ರೀತಿಯಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಸಿದ್ಧಾಂತವು ನಿರ್ಣಾಯಕವಲ್ಲ, ಮ್ಯಾಟಿಯಾಸೆವಿಚ್ನ ಪ್ರಮೇಯದಿಂದ ಅಸ್ತಿತ್ವವಾದದ ವಾಕ್ಯಗಳಿಗೆ (ಡಯೋಫಂಟೈನ್ ಸಮೀಕರಣಗಳು) ಸಹ. ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತವು ವಾಕ್ಯಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಮೊದಲ-ಕ್ರಮಾಂಕದ ಸಿದ್ಧಾಂತದ ತುಣುಕು, ಇದರಲ್ಲಿ ಎಲ್ಲಾ ಪರಿಮಾಣಕಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿರುತ್ತವೆ ಮತ್ತು ಅವು ಇತರ ಯಾವುದೇ ಚಿಹ್ನೆಗಳ ಮೊದಲು ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆ. ಅಂದರೆ, ಇದು ರೂಪದ ಎಲ್ಲಾ ನಿಜವಾದ ವಾಕ್ಯಗಳ ಗುಂಪಾಗಿದ್ದು, ಅಲ್ಲಿ ನೈಜ ಬಹುಪದಗಳ ಸಮಾನತೆಗಳು ಮತ್ತು ಅಸಮಾನತೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕ್ವಾಂಟಿಫೈಯರ್-ಫ್ರೀ ಸೂತ್ರವಾಗಿದೆ. ನಿರ್ದಿಷ್ಟ ವಾಕ್ಯವು ಈ ಸಿದ್ಧಾಂತಕ್ಕೆ ಸೇರಿದೆಯೇ ಎಂಬುದನ್ನು ಪರೀಕ್ಷಿಸುವ ಅಲ್ಗಾರಿದಮಿಕ್ ಸಮಸ್ಯೆಯು ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯಾಗಿದೆ; ಸಮಾನವಾಗಿ, ಮೂಲ ವಾಕ್ಯರಚನೆಯ ಪರೀಕ್ಷೆಗಳಲ್ಲಿ ಉತ್ತೀರ್ಣರಾದ ತಂತಿಗಳಿಗೆ (ಅವು ಸರಿಯಾದ ವಾಕ್ಯರಚನೆಯೊಂದಿಗೆ ಸರಿಯಾದ ಚಿಹ್ನೆಗಳನ್ನು ಬಳಸುತ್ತವೆ, ಮತ್ತು ಯಾವುದೇ ಪ್ರಮಾಣೀಕರಿಸದ ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ) ಇದು ವಾಕ್ಯವು ನೈಜ ಸಂಖ್ಯೆಗಳ ಬಗ್ಗೆ ನಿಜವಾದ ಹೇಳಿಕೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ನಿಜವಾಗಿರುವ ನೈಜ ಸಂಖ್ಯೆಗಳ-ಟುಪಲ್ಗಳ ಗುಂಪನ್ನು ಅರೆ ಬೀಜಗಣಿತದ ಸೆಟ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ನೈಜಗಳ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯನ್ನು ಕೊಟ್ಟಿರುವ ಅರೆ ಬೀಜಗಣಿತದ ಸೆಟ್ ಖಾಲಿ ಇದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವಂತೆ ಸಮಾನವಾಗಿ ಮರುಹೊಂದಿಸಬಹುದು. ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗಾಗಿ ಕ್ರಮಾವಳಿಗಳ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ನಿರ್ಧರಿಸುವಲ್ಲಿ, ಇನ್ಪುಟ್ನ ಗಾತ್ರದ ಅಳತೆಯನ್ನು ಹೊಂದಿರುವುದು ಮುಖ್ಯವಾಗಿದೆ. ಈ ರೀತಿಯ ಸರಳ ಅಳತೆಯು ವಾಕ್ಯದ ಉದ್ದವಾಗಿದೆಃ ಅಂದರೆ, ಅದು ಒಳಗೊಂಡಿರುವ ಚಿಹ್ನೆಗಳ ಸಂಖ್ಯೆ. ಆದಾಗ್ಯೂ, ಈ ಸಮಸ್ಯೆಯ ಕ್ರಮಾವಳಿಗಳ ನಡವಳಿಕೆಯ ಬಗ್ಗೆ ಹೆಚ್ಚು ನಿಖರವಾದ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಸಾಧಿಸಲು, ಇನ್ಪುಟ್ ಗಾತ್ರವನ್ನು ಹಲವಾರು ಅಸ್ಥಿರಗಳಾಗಿ ವಿಂಗಡಿಸುವುದು ಅನುಕೂಲಕರವಾಗಿದೆ, ಪ್ರಮಾಣೀಕರಿಸಬೇಕಾದ ಅಸ್ಥಿರಗಳ ಸಂಖ್ಯೆ, ವಾಕ್ಯದೊಳಗಿನ ಬಹುಪದಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ಈ ಬಹುಪದಗಳ ಮಟ್ಟ. ಉದಾಹರಣೆಗಳು ಸುವರ್ಣ ಅನುಪಾತವನ್ನು ಬಹುಪದದ ಮೂಲ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಈ ಬಹುಪದವು ಎರಡು ಮೂಲಗಳನ್ನು ಹೊಂದಿದೆ, ಅವುಗಳಲ್ಲಿ ಕೇವಲ ಒಂದು (ಚಿನ್ನದ ಅನುಪಾತ) ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿದೆ. ಹೀಗಾಗಿ, ಸುವರ್ಣ ಅನುಪಾತದ ಅಸ್ತಿತ್ವವನ್ನು ವಾಕ್ಯದಿಂದ ವ್ಯಕ್ತಪಡಿಸಬಹುದು ಏಕೆಂದರೆ ಸುವರ್ಣ ಅನುಪಾತವು ಅತೀಂದ್ರಿಯವಲ್ಲ, ಇದು ನಿಜವಾದ ವಾಕ್ಯವಾಗಿದೆ ಮತ್ತು ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಸೇರಿದೆ. ಈ ವಾಕ್ಯವನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ನೀಡಿದರೆ, ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗೆ ಉತ್ತರವೆಂದರೆ ಬೂಲಿಯನ್ ಮೌಲ್ಯವು ನಿಜವಾಗಿದೆ. ಅಂಕಗಣಿತ ಮತ್ತು ಜ್ಯಾಮಿತೀಯ ವಿಧಾನಗಳ ಅಸಮಾನತೆಯು, ಪ್ರತಿ ಎರಡು ಋಣಾತ್ಮಕವಲ್ಲದ ಸಂಖ್ಯೆಗಳಿಗೆ ಮತ್ತು ಈ ಕೆಳಗಿನ ಅಸಮಾನತೆಯು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಹೇಳುತ್ತದೆಃ ಮೇಲೆ ತಿಳಿಸಿದಂತೆ, ಇದು ನೈಜ ಸಂಖ್ಯೆಗಳ ಬಗ್ಗೆ ಮೊದಲ ಕ್ರಮಾಂಕದ ವಾಕ್ಯವಾಗಿದೆ, ಆದರೆ ಅಸ್ತಿತ್ವವಾದದ ಪರಿಮಾಣಕಗಳಿಗಿಂತ ಸಾರ್ವತ್ರಿಕವಾದದ್ದು, ಮತ್ತು ವಿಭಜನೆ, ವರ್ಗಮೂಲಗಳು ಮತ್ತು ವಾಸ್ತವದ ಮೊದಲ ಕ್ರಮಾಂಕದ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಅನುಮತಿಸದ ಸಂಖ್ಯೆ 2 ಗೆ ಹೆಚ್ಚುವರಿ ಚಿಹ್ನೆಗಳನ್ನು ಬಳಸುವ ವಾಕ್ಯವಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಎರಡೂ ಬದಿಗಳನ್ನು ವರ್ಗಗೊಳಿಸುವ ಮೂಲಕ ಇದನ್ನು ಈ ಕೆಳಗಿನ ಅಸ್ತಿತ್ವವಾದದ ಹೇಳಿಕೆಯಾಗಿ ಪರಿವರ್ತಿಸಬಹುದು, ಇದನ್ನು ಅಸಮಾನತೆಯು ಯಾವುದೇ ವ್ಯತಿರಿಕ್ತ ಉದಾಹರಣೆಗಳನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಕೇಳುವಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದುಃ ಈ ವಾಕ್ಯವನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ನೀಡಿದರೆ, ವಾಸ್ತವಿಕ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗೆ ಉತ್ತರವೆಂದರೆ ಬೂಲಿಯನ್ ಮೌಲ್ಯವು ತಪ್ಪಾಗಿದೆಃ ಯಾವುದೇ ವ್ಯತಿರಿಕ್ತ ಉದಾಹರಣೆಗಳಿಲ್ಲ. ಆದ್ದರಿಂದ, ಈ ವಾಕ್ಯವು ಸರಿಯಾದ ವ್ಯಾಕರಣದ ರೂಪದಲ್ಲಿದೆಯಾದರೂ, ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಸೇರಿಲ್ಲ. ಅಲ್ಗಾರಿದಮ್ಗಳು ಆಲ್ಫ್ರೆಡ್ ಟಾರ್ಸ್ಕಿಯ ಕ್ವಾಂಟಿಫೈಯರ್ ಎಲಿಮಿನೇಷನ್ ವಿಧಾನವು (1948) ರಿಯಾಲ್ಗಳ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತವನ್ನು (ಮತ್ತು ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ ರಿಯಾಲ್ಗಳ ಮೊದಲ ಕ್ರಮದ ಸಿದ್ಧಾಂತ) ಅಲ್ಗಾರಿದಮಿಕ್ ಆಗಿ ಪರಿಹರಿಸಬಹುದಾದಂತೆ ತೋರಿಸಿದೆ, ಆದರೆ ಅದರ ಸಂಕೀರ್ಣತೆಯ ಮೇಲೆ ಪ್ರಾಥಮಿಕ ಬಂಧವಿಲ್ಲ. ಜಾರ್ಜ್ ಇ. ಕಾಲಿನ್ಸ್ (1975) ಅವರ ಸಿಲಿಂಡರಾಕಾರದ ಬೀಜಗಣಿತದ ವಿಭಜನೆಯ ವಿಧಾನವು ಸಮಯದ ಅವಲಂಬನೆಯನ್ನು ದ್ವಿಗುಣ ಘಾತಾಂಕಕ್ಕೆ ಸುಧಾರಿಸಿತು, ವಾಕ್ಯದಲ್ಲಿನ ಗುಣಾಂಕಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಅಗತ್ಯವಿರುವ ಬಿಟ್ಗಳ ಸಂಖ್ಯೆ, ಅದರ ಮೌಲ್ಯವನ್ನು ನಿರ್ಧರಿಸಬೇಕಾಗಿದೆ, ಇದು ವಾಕ್ಯದಲ್ಲಿನ ಬಹುಪದಗಳ ಸಂಖ್ಯೆ, ಅವುಗಳ ಒಟ್ಟು ಪದವಿ ಮತ್ತು ಅಸ್ಥಿರಗಳ ಸಂಖ್ಯೆ. 1988 ರ ಹೊತ್ತಿಗೆ, ದಿಮಾ ಗ್ರಿಗೊರೀವ್ ಮತ್ತು ನಿಕೋಲಾಯ್ ವೊರೊಬ್ಜೋವ್ ಅವರು ಸಂಕೀರ್ಣತೆಯನ್ನು ಬಹುಪದದಲ್ಲಿ ಘಾತೀಯವೆಂದು ತೋರಿಸಿದ್ದರು, ಮತ್ತು 1992 ರಲ್ಲಿ ಪ್ರಕಟವಾದ ಪ್ರಬಂಧಗಳ ಸರಣಿಯಲ್ಲಿ ಜೇಮ್ಸ್ ರೆನೆಗರ್ ಇದನ್ನು ಏಕ ಘಾತೀಯ ಅವಲಂಬನೆಗೆ ಸುಧಾರಿಸಿದರು. ಈ ಕ್ರಮಾವಳಿಗಳ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯು ತಪ್ಪುದಾರಿಗೆಳೆಯುವಂತಿರಬಹುದು, ಏಕೆಂದರೆ ಆಚರಣೆಯಲ್ಲಿ ಅವುಗಳನ್ನು ಬಹಳ ಸಣ್ಣ ಗಾತ್ರದ ಒಳಹರಿವಿನ ಮೇಲೆ ಮಾತ್ರ ಚಲಾಯಿಸಬಹುದು. 1991ರ ಹೋಲಿಕೆಯಲ್ಲಿ, ಹೂನ್ ಹಾಂಗ್ ಅಂದಾಜಿನ ಪ್ರಕಾರ, ಕಾಲಿನ್ಸ್ನ ದ್ವಿಗುಣ ಘಾತೀಯ ಕಾರ್ಯವಿಧಾನವು ಮೇಲಿನ ಎಲ್ಲಾ ನಿಯತಾಂಕಗಳನ್ನು ಸೆಕೆಂಡಿಗಿಂತ ಕಡಿಮೆ ಅವಧಿಯಲ್ಲಿ 2ಕ್ಕೆ ಹೊಂದಿಸುವ ಮೂಲಕ ವಿವರಿಸಲಾದ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ, ಆದರೆ ಗ್ರಿಗೊರೀವ್, ವೋರ್ಬ್ಜೋವ್ ಮತ್ತು ರೆನೆಗರ್ ಅವರ ಕ್ರಮಾವಳಿಗಳು ಬದಲಿಗೆ ಒಂದು ದಶಲಕ್ಷ ವರ್ಷಗಳಿಗಿಂತ ಹೆಚ್ಚು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತವೆ. 1993 ರಲ್ಲಿ, ಜೂಸ್, ರಾಯ್ ಮತ್ತು ಸೊಲೆರ್ನೋ ಅವರು ಘಾತೀಯ-ಸಮಯದ ಕಾರ್ಯವಿಧಾನಗಳಿಗೆ ಸಣ್ಣ ಮಾರ್ಪಾಡುಗಳನ್ನು ಮಾಡಲು ಸಾಧ್ಯವಿದೆ ಎಂದು ಸೂಚಿಸಿದರು, ಅವುಗಳನ್ನು ಪ್ರಾಯೋಗಿಕವಾಗಿ ಸಿಲಿಂಡರಾಕಾರದ ಬೀಜಗಣಿತದ ನಿರ್ಧಾರಕ್ಕಿಂತ ವೇಗವಾಗಿ ಮತ್ತು ಸಿದ್ಧಾಂತದಲ್ಲಿ ವೇಗವಾಗಿ ಮಾಡಲು ಸಾಧ್ಯವಿದೆ. ಆದಾಗ್ಯೂ, 2009 ರ ಹೊತ್ತಿಗೆ, ವಾಸ್ತವಿಕತೆಯ ಮೊದಲ-ಕ್ರಮಾಂಕದ ಸಿದ್ಧಾಂತದ ಸಾಮಾನ್ಯ ವಿಧಾನಗಳು ವಾಸ್ತವಿಕತೆಯ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತಕ್ಕೆ ವಿಶೇಷವಾದ ಏಕವಾದ ಘಾತೀಯ ಕ್ರಮಾವಳಿಗಳಿಗಿಂತ ಆಚರಣೆಯಲ್ಲಿ ಉತ್ತಮವಾಗಿವೆ. ಕಂಪ್ಯುಟೇಷನಲ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಮತ್ತು ಜ್ಯಾಮಿತೀಯ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಹಲವಾರು ಸಮಸ್ಯೆಗಳನ್ನು ವಾಸ್ತವಿಕ ಅಸ್ತಿತ್ವದ ಸಿದ್ಧಾಂತಕ್ಕಾಗಿ ಕಂಪ್ಲೀಟ್ ಎಂದು ವರ್ಗೀಕರಿಸಬಹುದು. ಅಂದರೆ, ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸಮಸ್ಯೆಯು ಈ ಸಮಸ್ಯೆಗಳ ಒಂದು ನಿದರ್ಶನಕ್ಕೆ ಬಹುಪದ-ಸಮಯದ ಅನೇಕ-ಒಂದು ಕಡಿತವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಪ್ರತಿಯಾಗಿ ಈ ಸಮಸ್ಯೆಗಳು ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಕಡಿಮೆಯಾಗುತ್ತವೆ. ಈ ರೀತಿಯ ಹಲವಾರು ಸಮಸ್ಯೆಗಳು ಒಂದು ನಿರ್ದಿಷ್ಟ ರೀತಿಯ ಇಂಟರ್ಸೆಕ್ಷನ್ ಗ್ರಾಫ್ಗಳ ಗುರುತಿಸುವಿಕೆಗೆ ಸಂಬಂಧಿಸಿವೆ. ಈ ಸಮಸ್ಯೆಗಳಲ್ಲಿ, ಇನ್ಪುಟ್ ಒಂದು ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ ಆಗಿದೆ; ಒಂದು ನಿರ್ದಿಷ್ಟ ವರ್ಗದ ಆಕಾರಗಳಿಂದ ಜ್ಯಾಮಿತೀಯ ಆಕಾರಗಳನ್ನು ಗ್ರಾಫ್ನ ಶೃಂಗಗಳೊಂದಿಗೆ ಸಂಯೋಜಿಸಬಹುದೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಗುರಿಯಾಗಿದೆ, ಅವುಗಳ ಸಂಬಂಧಿತ ಆಕಾರಗಳು ಖಾಲಿ ಇಲ್ಲದ ಛೇದನವನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ನಲ್ಲಿ ಎರಡು ಶೃಂಗಗಳು ಪಕ್ಕದಲ್ಲಿರುತ್ತವೆ. ವಾಸ್ತವದ ಅಸ್ತಿತ್ವದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಸಂಪೂರ್ಣವಾದ ಈ ರೀತಿಯ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಸಮತಲದಲ್ಲಿನ ರೇಖೆಯ ಭಾಗಗಳ ಛೇದಕ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಗುರುತಿಸುವುದು, ಘಟಕ ಡಿಸ್ಕ್ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಗುರುತಿಸುವುದು ಮತ್ತು ಸಮತಲದಲ್ಲಿನ ಕನ್ವೆಕ್ಸ್ ಸೆಟ್ಗಳ ಛೇದಕ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಗುರುತಿಸುವುದು ಸೇರಿವೆ. ಕ್ರಾಸಿಂಗ್ಗಳಿಲ್ಲದ ಸಮತಲದಲ್ಲಿ ಚಿತ್ರಿಸಲಾದ ಗ್ರಾಫ್ಗಳಿಗೆ, ಗ್ರಾಫ್ನ ಅಂಚುಗಳನ್ನು ನೇರ ರೇಖೆಯ ಭಾಗಗಳಾಗಿ ಚಿತ್ರಿಸಲಾಗಿದೆಯೇ ಅಥವಾ ಅನಿಯಂತ್ರಿತ ವಕ್ರಾಕೃತಿಗಳಾಗಿ ಚಿತ್ರಿಸಲಾಗಿದೆಯೇ ಎಂಬುದನ್ನು ಲೆಕ್ಕಿಸದೆ ಒಂದೇ ವರ್ಗದ ಸಮತಟ್ಟಾದ ಗ್ರಾಫ್ಗಳನ್ನು ಪಡೆಯಲಾಗುತ್ತದೆ ಎಂದು ಫೇರಿಯ ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಆದರೆ ಈ ಸಮಾನತೆಯು ಇತರ ರೀತಿಯ ರೇಖಾಚಿತ್ರಗಳಿಗೆ ಅನ್ವಯಿಸುವುದಿಲ್ಲ. ಉದಾಹರಣೆಗೆ, ರೇಖಾಚಿತ್ರದ ದಾಟುವ ಸಂಖ್ಯೆಯನ್ನು (ಅನಿಯಂತ್ರಿತವಾಗಿ ಬಾಗಿದ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿನ ದಾಟುವಿಕೆಯ ಕನಿಷ್ಠ ಸಂಖ್ಯೆ) ಎನ್. ಪಿ. ಯಲ್ಲಿ ನಿರ್ಧರಿಸಬಹುದಾದರೂ, ಆಯತಾಕಾರದ ದಾಟುವಿಕೆಯ ಸಂಖ್ಯೆಯ ಮೇಲೆ ನೀಡಲಾದ ಬಂಧವನ್ನು ಸಾಧಿಸುವ ರೇಖಾಚಿತ್ರವಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಪೂರ್ಣವಾಗಿದೆ (ಸಮತಲದಲ್ಲಿ ನೇರ ರೇಖೆಯ ಭಾಗಗಳಾಗಿ ಎಳೆಯಲಾದ ಅಂಚುಗಳೊಂದಿಗೆ ಯಾವುದೇ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ದಾಟುವ ಕನಿಷ್ಠ ಜೋಡಿ ಅಂಚುಗಳ ಸಂಖ್ಯೆ). ನಿರ್ದಿಷ್ಟ ರೇಖಾಚಿತ್ರವನ್ನು ಸಮತಲದಲ್ಲಿ ನೇರ ರೇಖೆಯ ಅಂಚುಗಳೊಂದಿಗೆ ಮತ್ತು ನಿರ್ದಿಷ್ಟ ಅಂಚಿನ ಜೋಡಿಗಳನ್ನು ಅದರ ದಾಟುವಿಕೆಯೊಂದಿಗೆ ಎಳೆಯಬಹುದೇ ಅಥವಾ ಸಮಾನವಾಗಿ, ದಾಟುವಿಕೆಯೊಂದಿಗೆ ಬಾಗಿದ ರೇಖಾಚಿತ್ರವನ್ನು ಅದರ ದಾಟುವಿಕೆಯನ್ನು ಸಂರಕ್ಷಿಸುವ ರೀತಿಯಲ್ಲಿ ನೇರಗೊಳಿಸಬಹುದೇ ಎಂದು ಪರೀಕ್ಷಿಸಲು ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತವು ಸಹ ಪೂರ್ಣವಾಗಿದೆ. ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ಇತರ ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಗಳೆಂದರೆಃ ಒಂದು ನಿರ್ದಿಷ್ಟ ಬಹುಭುಜಾಕೃತಿಯ ಎಲ್ಲಾ ಬಿಂದುಗಳು ಗೋಚರಿಸುವ ಅತಿ ಕಡಿಮೆ ಸಂಖ್ಯೆಯ ಬಿಂದುಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ಆರ್ಟ್ ಗ್ಯಾಲರಿ ಸಮಸ್ಯೆ. ನರ ಜಾಲಗಳಿಗೆ ತರಬೇತಿ ನೀಡುವುದು. ಒಂದು ನಿರ್ದಿಷ್ಟ ಗುಂಪಿನ ಬಹುಭುಜಾಕೃತಿಗಳು ನಿರ್ದಿಷ್ಟ ಚೌಕಾಕಾರದ ಧಾರಕದಲ್ಲಿ ಹೊಂದಿಕೊಳ್ಳಬಹುದೇ ಎಂದು ನಿರ್ಧರಿಸುವ ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆ. ಯುನಿಟ್ ಡಿಸ್ಟೆನ್ಸ್ ಗ್ರಾಫ್ಗಳ ಗುರುತಿಸುವಿಕೆ, ಮತ್ತು ಗ್ರಾಫ್ನ ಆಯಾಮ ಅಥವಾ ಯೂಕ್ಲಿಡಿಯನ್ ಆಯಾಮವು ಗರಿಷ್ಠ ಒಂದು ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯವಾಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವುದು. ಸೂಡೋಲಿನ್ಗಳ ಹಿಗ್ಗುವಿಕೆ (ಅಂದರೆ, ಸಮತಲದಲ್ಲಿನ ವಕ್ರಾಕೃತಿಗಳ ಒಂದು ಕುಟುಂಬವನ್ನು ನೀಡಿದರೆ, ಅವು ರೇಖೆಯ ಜೋಡಣೆಗೆ ಹೋಮೋಮಾರ್ಫಿಕ್ ಆಗಿವೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುತ್ತದೆ); ಯಾವುದೇ ಸ್ಥಿರ ಆಯಾಮ> 2 ರಲ್ಲಿ ಜ್ಯಾಮಿತೀಯ ಕ್ವಾಂಟಮ್ ತರ್ಕದ ದುರ್ಬಲ ಮತ್ತು ಬಲವಾದ ತೃಪ್ತಿ ಎರಡೂ; ನಿಸ್ಸಂದಿಗ್ಧವಾದ ಸ್ವಯಂಚಾಲಿತಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಮಾದರಿ ಪರಿಶೀಲನಾ ಮಧ್ಯಂತರ ಮಾರ್ಕೋವ್ ಸರಪಳಿಗಳು. ಅಲ್ಗಾರಿದಮಿಕ್ ಸ್ಟೈನಿಟ್ಜ್ ಸಮಸ್ಯೆ (ಜಾಲರಿಯನ್ನು ನೀಡಿದರೆ, ಅದು ಕನ್ವೆಕ್ಸ್ ಪಾಲಿಟೋಪ್ನ ಫೇಸ್ ಲ್ಯಾಟಿಸ್ ಆಗಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುತ್ತದೆ), 4-ಆಯಾಮದ ಪಾಲಿಟೋಪ್ಗಳಿಗೆ ಸೀಮಿತವಾಗಿದ್ದರೂ ಸಹ; ಕೆಲವು ಕನ್ವೆಕ್ಸ್ ಕಾಯಗಳ ವ್ಯವಸ್ಥೆಗಳ ಸಾಕ್ಷಾತ್ಕಾರ ಸ್ಥಳಗಳು ಬಹು-ಆಟಗಾರ ಆಟಗಳ ನ್ಯಾಶ್ ಸಮತೋಲನದ ವಿವಿಧ ಗುಣಲಕ್ಷಣಗಳನ್ನು ತ್ರಿಕೋನಗಳು ಮತ್ತು ಚತುರ್ಭುಜಗಳ ನಿರ್ದಿಷ್ಟ ಅಮೂರ್ತ ಸಂಕೀರ್ಣವನ್ನು ಮೂರು ಆಯಾಮದ ಯೂಕ್ಲಿಡಿಯನ್ ಜಾಗದಲ್ಲಿ ಹುದುಗಿಸುತ್ತದೆ; ಸಮತಲದಲ್ಲಿ ಹಂಚಿಕೊಂಡ ಶೃಂಗದ ಮೇಲೆ ಅನೇಕ ಗ್ರಾಫ್ಗಳನ್ನು ಹುದುಗಿಸುವುದು ಇದರಿಂದ ಎಲ್ಲಾ ಗ್ರಾಫ್ಗಳನ್ನು ದಾಟದೆ ಚಿತ್ರಿಸಲಾಗುತ್ತದೆ; ಪ್ಲ್ಯಾನರ್ ಪಾಯಿಂಟ್ ಸೆಟ್ಗಳ ಗೋಚರತೆ ಗ್ರಾಫ್ಗಳನ್ನು ಗುರುತಿಸುವುದು; (ಪ್ರೊಜೆಕ್ಟಿವ್ ಅಥವಾ ನಾನ್-ಟ್ರಿವಿಯಲ್ ಅಫೈನ್) ಅಡ್ಡ ಉತ್ಪನ್ನದ ಮೇಲೆ ಎರಡು ಪದಗಳ ನಡುವಿನ ಸಮೀಕರಣದ ತೃಪ್ತಿಯನ್ನು ನಿರ್ಧರಿಸುವುದು; ಕನಿಷ್ಠ ಇಳಿಜಾರಿನ ಸಂಖ್ಯೆಯನ್ನು ನಿರ್ಧರಿಸುವುದು. ಕಡಿಮೆ ಶ್ರೇಣಿಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆ ಸಮಸ್ಯೆ. ಇದರ ಆಧಾರದ ಮೇಲೆ, ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವನ್ನು ವಾಸ್ತವದ ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತಕ್ಕೆ ಬಹುಪದ-ಸಮಯದ ಅನೇಕ-ಒಂದು ಕಡಿತವನ್ನು ಹೊಂದಿರುವ ಸಮಸ್ಯೆಗಳ ಗುಂಪು ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಹಿಲ್ಬರ್ಟ್ನ ಹತ್ತನೇ ಸಮಸ್ಯೆಯನ್ನು ಸಹ ನೋಡಿ, ಪೂರ್ಣಾಂಕಗಳ (ಅನಿಶ್ಚಿತ) ಅಸ್ತಿತ್ವವಾದದ ಸಿದ್ಧಾಂತದ ಮೇಲೆ ಉಲ್ಲೇಖಗಳು ವಾಸ್ತವಿಕ ಬೀಜಗಣಿತದ ಜ್ಯಾಮಿತಿಯ ಅಂಕಗಣಿತದ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯ ಔಪಚಾರಿಕ ಸಿದ್ಧಾಂತಗಳು.