I.

In June of 1998, Petitioner Moran commenced this Article 78 proceeding seeking, in relevant part, to overturn the Department of Taxation and Finance's decision denying its request for a refund of taxes paid under Article 13-A of the Tax Law. Moran also challenged, as facially unconstitutional under the Commerce Clause (US Const, art I, § 8, cl 3), those portions of Tax Law §§ 301 and 301-a (hereafter the Petroleum Business Tax or PBT) imposing a tax on fuel imported by a vessel for its consumption within the State while engaged in interstate commerce. Moran further contested the Legislature's retroactive application of the 1997 amendments to the PBT. Eklof and Reinauer,[1] similarly denied refunds of taxes paid pursuant to the PBT, were granted permission to intervene in March of 1999. Intervenor Eklof is a New York corporation with its principal place of business in Staten Island. Intervenor Reinauer was a New York corporation until 1993, when it became a Delaware limited partnership. Reinauer maintains its principal office in Staten Island. The intervenors operate tugboats and barges transporting cargo throughout the waters of the East Coast, including the waters of New York.[2] Supreme Court granted the Commissioner's motion to dismiss the petition for failure to exhaust administrative remedies. The court also found that the 1997 amendments to the PBT creating a retroactive adjustment to the Tax Law did not contravene the Due Process Clause of the 14th Amendment to the United States Constitution. On appeal, the Appellate Division reversed and declared the tax on the consumption of fuel in sections 301(a)(1)(ii), 301-a(b)(2) and 301-a(c)(1)(B) of the Tax Law facially unconstitutional under the Commerce Clause (283 2 78 [2001]). The Appellate Division noted that the petitioners and intervenors were being taxed on the consumption of fuel that had not “been removed from the stream of interstate commerce” and had not “come to rest” within New York (283 2 at 83). The court found that the challenged statute was unconstitutional because it artificially imposed a substantial nexus with New York, such “that an activity previously identified as simple interstate movement is now, without more, 'deemed to constitute a taxable use'” (283 2 at 83 [citations omitted]). Subsequently, the Commissioner moved in Supreme Court for a final judgment consistent with the Appellate Division order. Eklof and Reinauer cross-moved for an order granting a refund of taxes paid and attorneys' fees. The court reluctantly granted the Commissioner's motion for an order declaring Tax Law §§ 301(a)(1)(ii), 301-a(b)(2) and 301-a(c)(1)(B) facially unconstitutional. Supreme Court denied the intervenors' claim for tax refunds for their failure to exhaust administrative remedies and denied the application for attorneys' fees. The Commissioner appeals as of right on constitutional grounds from the judgment of Supreme Court, bringing up for review the non- final order of the Appellate Division. We now reverse.

II.

The PBT imposes a tax on petroleum businesses “for the privilege of engaging in business, doing business, employing capital, owning or leasing property, or maintaining an office in this state” (Tax Law §§ 301[a][1], 301-a[a]). Intervenors qualify as petroleum businesses under section 300(b)(1)(i) of the Tax Law as businesses that cause fuel to be imported into the State for their own use. From 1984 through August of 1990, an annual “privilege tax” was imposed on each petroleum business calculated as a percentage of “the consideration given or contracted to be given by it for petroleum * * * which it imported or caused to be imported * * * into this state for consumption by it in this state” (Tax Law § 301[a][1][ii]). The statute further provides that “[a] petroleum business, which brings petroleum into this state in the fuel tank connecting with the engine of a vessel propelled by the use of such petroleum” shall receive a credit equal to the amount of gallons of fuel purchased in New York against the total gallons consumed by the business in New York (Tax Law § 301[c]). Since September 1990, the “privilege tax” is a monthly tax calculated on a cents-per-gallon basis ( see Tax Law § 301-a). The statute now provides that “fuel brought into this state in the fuel tank connecting with the engine of a vessel propelled by the use of such motor fuel shall be deemed to constitute a taxable use of motor fuel * * * to the extent that the fuel is consumed in the operation of the vessel in this state” (Tax Law § 301-a[b][2], see Tax Law § 301-a[c][1][B]).[3] Section 301-a also provides a credit for the fuel a petroleum business has purchased in New York ( see Tax Law § 301-a[b][2] & 301-a[c][1][B]). These statutes reflect the amendments enacted in 1997 in response to Matter of Tug Buster Bouchard Corp. v Wetzler, 217 AD2d 192 [3d Dept 1996], affd , 89 NY2d 830 [1996], which declared Tax Law § 301(a)(1)(ii) unconstitutional. The 1997 amendments added Tax Law §§ 301(c), 301-a(b)(2) and 301-a(c)(1)(B) ( see 1997 McKinney's Session Laws of NY, at 693-694).[4] Section 301(c) was to apply retroactively to April 1, 1984 and the amendments to section 301-a were to apply retroactively to September 1, 1990 ( see 1997 McKinney's Session Laws of NY, at 711).

III.

At the outset, we note that intervenors are making a facial challenge to the constitutionality of the PBT. In order to prevail, they must surmount the presumption of constitutionality accorded to legislative enactments by proof “beyond a reasonable doubt” ( see LaValle v Hayden, , 98 NY2d 155, 161 [2002]). A party mounting a facial constitutional challenge bears the substantial burden of demonstrating “that 'in any degree and in every conceivable application,' the law suffers wholesale constitutional impairment” ( Cohen v State of New >,, 94 NY2d 1, 8 [1999]). In other words, “the challenger must establish that no set of circumstances exists under which the Act would be valid” ( United States v Salerno, 481 US 739, 745 [1987]). Early United States Supreme Court decisions held that States were unable to impose direct taxes on interstate commerce ( see e.g. Helson v Kentucky, 279 US 245, 248 [1929]). This line of reasoning has subsequently evolved to recognize that interstate commerce can be made to bear its portion of State taxes ( see Complete Auto Transit, Inc. v Brady, 430 US 274, 288 [1977], citing Western Live Stock v Bureau of Revenue, 303 US 250, 254 [1938], Colonial Pipeline Co. v Triagle, 421 US 100, 108 [1975]). Currently, a four-prong test is in place to determine whether a State tax imposed upon interstate commerce will survive a challenge under the Commerce Clause. The validity of the tax will be upheld “[1] when the tax is applied to an activity with a substantial nexus with the taxing State, [2] is fairly apportioned, [3] does not discriminate against interstate commerce, and [4] is fairly related to the services provided by the State” ( Complete Auto, 430 US at 279). The only portion of the Complete Auto test at issue in the present appeal is whether a substantial nexus could exist between New York and the activity to which the statutes at issue apply. Intervenors' primary argument is that the fuel consumed in interstate commerce can never have a nexus with a taxing State because it does not “come to rest” within the State. For this proposition, they rely on a line of cases decided prior to Complete Auto ( see Helson & Randolph v Kentucky, 279 US 245 [1929], Edelman v Boeing Air Transp., 289 US 249 [1933], United Air Lines v Mahin, 410 US 623 [1973]). These cases, decided at a time when States were prevented from taxing interstate commerce directly, draw a distinction between an approved tax on the withdrawal of fuel from storage for use in interstate commerce and a tax on the mere consumption of fuel in interstate commerce, which at that time was seen to be unconstitutional. The Supreme Court of the United States has since determined that whether items remained “in the stream of interstate commerce” or “came to rest” within the State “may be of some importance for other purposes * * * but for Commerce Clause analysis it is largely irrelevant” ( D.H. Holmes Co. v McNamara, 486 US 24, 31 1987] [use tax imposed on catalogs mailed to customers within the State]). The Appellate Division erred when it applied the pre- Complete Auto cases to this case. We have previously addressed what constitutes a substantial nexus for the purpose of Commerce Clause analysis in the context of sales and use taxes ( see Matter of Orvis Co., Inc. v Tax Appeals Tribunal, , 86 NY2d 165 [1995]). Orvis examined the development of Supreme Court jurisprudence concerning the type of nexus required before a State could impose a valid tax on interstate commerce ( see Orvis, 86 NY2d at 170-178). That development culminated with the Supreme Court's decision in Quill Corp. v North Dakota, 504 US 298 (1992), and held that the substantial nexus portion of the Complete Auto test requires the physical presence within the State of the entity being taxed ( see Orvis, 86 NY2d at 178). “While a physical presence * * * is required, it need not be substantial. Rather, it must be demonstrably more than a 'slightest presence'” ( Orvis, 86 NY2d at 178, citing National Geographic v California Equalization Bd., 430 US 551, 556 [1977]). Moreover, “the required nexus with the taxing State need not necessarily be directly related to the activity being taxed, but [could] simply [be] whether the facts demonstrate some definite link, some minimum connection, between [the taxing State and] the person * * * it seeks to tax” ( Orvis, 86 NY2d at 174 [citations and internal quotation marks omitted, emphasis in original]). Other States have also addressed the nexus prong of the Complete Auto test. While not binding, these cases inform our inquiry. In Western Maryland Railway Co. v Goodwin, 282 SE2d 240 [W Va 1981] appeal dismissed 456 US 952 [1982]), the Supreme Court of Appeals of West Virginia found that “purposive, revenue generating activities in the State are sufficient to render a person liable for taxes” ( Western Maryland, 282 SE2d at 244). The same Court subsequently addressed the constitutionality of an excise tax imposed upon motor carriers for the use or consumption within the State of fuel purchased outside of the State ( see Hartley Marine Corp. v Mierke, 474 SE2d 599, 602 [W Va 1996] cert denied 519 US 1108 [1997]). Among other things, the Court found the requisite nexus had been established by the taxpayers' maintenance of offices and employees, the ownership of real property and the transportation of goods to and from businesses within the State ( see Hartley, 474 SE2d at 609). The Supreme Court of Iowa, addressing whether a State excise tax discriminated against railroads, compared a sales tax levied on fuel purchased within the State for use by barges with the excise tax imposed on railroads ( see Atchison, Topeka & Santa Fe Railway Co. v Bair, 338 NW2d 338, 347 [1983] cert denied 465 US 1071 [1984]). The Court, applying Complete Auto, held that the State had a sufficient relationship with the vessel traffic in its waters to satisfy the substantial nexus requirement ( see Atchison, 338 NW2d at 347). These decisions support our conclusion that the Complete Auto test is the appropriate test to determine whether these statutes violate the Commerce Clause. Further, consistent with our decision in Orvis, they support the conclusion that physical presence of a business in this State is sufficient to constitute a “substantial nexus” with the State under Complete Auto. The fact that the tax is measured by the consumption of fuel within the State does not alter the State's authority to tax the privilege of doing business in New York. Eklof and Reinauer also argue that a tax on a medium of interstate commerce is not permitted ( see Quill Corp. v North Dakota, 504 US 298 [1992]; National Bellas Hess, Inc. v Dept. of Revenue of Illinois, 386 US 753 [1967]; Helson v Kentucky, 279 US 245 [1929]). However, these cases are inapposite because as the statute makes clear, it is the privilege of doing business in the State, as measured by the consumption of fuel, that is being taxed here. For the purpose of this facial challenge, it is not necessary to address whether this tax would be constitutional as applied to a foreign business whose only connection with the State is its consumption of fuel as its ships pass through New York in the course of interstate commerce.

IV.

Thus, intervenors' facial constitutional challenge must fail because there is a set of circumstances under which the statute would be valid. A sufficient nexus would exist where the entity being taxed was, for example, a New York corporation, with offices in the State, employing New York citizens and conducting business in the State. This set of facts would constitute a physical presence that is more than a “slightest presence” in New York. Therefore, we conclude that a substantial nexus could exist such that the first prong of the Complete Auto test would be satisfied and the statute could survive a facial constitutional challenge. Intervenors further argue that the retroactive application of the 1997 amendments to the statutes is a due process violation. We remit this issue, and any other issues raised but not determined by the Appellate Division, to that court for its consideration. Accordingly, the judgment appealed from, and the order of the Appellate Division brought up for review, should be reversed, with costs, and the matter remitted to that court for further proceedings in accordance with this Opinion.